개발 블로그

문제 링크 : www.acmicpc.net/problem/16931

문제

크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다.

종이의 각 칸에 놓인 정육면체의 개수가 주어졌을 때, 이 도형의 겉넓이를 구하는 프로그램을 작성하시오.

위의 그림은 3×3 크기의 종이 위에 정육면체를 놓은 것이고, 겉넓이는 60이다.

입력

첫째 줄에 종이의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 종이의 각 칸에 놓인 정육면체의 수가 주어진다.

출력

첫째 줄에 도형의 겉넓이를 출력한다.

접근 방법

각 배열 칸에 대해 옆면 4개의 겉넓이를 구하고 마지막에 위(N*M)넓이와 아래(N*M)넓이를 더해줬다.

각 배열 칸에 대한 옆면의 넓이 4개를 구하는게 관건인데, 이는 인접한 배열칸의 높이와 현재 위치칸의 높이의 차를 이용해서 구할 수 있다.

1) 현재칸 높이 >= 인접한 칸 높이 -> 가려지지 않은 부분의 높이는 (현재-인접)

2) 현재칸 높이 =< 인접한 칸 높이 -> 다 가려져 버려서 높이는 0

이때 주의할 점은 가장자리 즉 가장 바깥쪽 옆면의 넓이인데, 이는 인접한 칸의 높이가 0이라고 생각하면 된다. 

만약 N=4, M=4이면

o 표시한 곳에 입력받은 숫자를 저장하고

그 주위로는 0을 저장해서 높이를 0으로 표시하면 쉽게 계산할 수 있다.

#include <iostream>


using namespace std;

int arr[102][102];			//가장 자리 처리를 위해서 

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};


int main(){
    
    int ans = 0;
    
    int N,M;
    cin>>N>>M;
    
    for(int i = 0; i<N+2; i++){		//가장 자리를 0으로 설정하기 위한 범위
        for(int j=0; j<M+2; j++){
            arr[i][j] = 0;
        }
    }
    
    for(int i = 1; i<=N; i++){			//가장 자리 빼고 안쪽에 숫자 입력 받음
        for(int j=1; j<=M; j++){
            cin>>arr[i][j];
        }
    }
    
    for(int r = 1; r<=N; r++){
        for(int c=1; c<=M; c++){
            
            for(int k = 0; k<4; k++){
                int nr = r+dr[k];
                int nc = c+dc[k];
                
                if(arr[r][c]>=arr[nr][nc]){			//현재 위치가 더 커서 위로 나올 때만 더함
                    ans+=arr[r][c] - arr[nr][nc];
                }
            }
            
            
        }
    }
    
    //위, 아래
    ans+=2*(N*M);
    cout << ans;
    
    return 0;
}