[ 백준 16931 ] 겉넓이 구하기 (C++)

백준의 겉넓이 구하기(16931) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 접근하는 방법이 중요한 문제인 것 같다.

   우리는 정육면체의 겉넓이를 구해야 한다.

   즉, 높이에 따라서 가려진 부분이 있을 수도 있고 튀어나온 부분이 있을 수도 있다. 이 떄, 가려진 부분은 계산을 안하고

   튀어나온 부분만 계산하면 된다. 이걸 어떻게 할까 ??

   바로 인접한 블록과의 높이를 비교하면 쉽게 구할 수 있다.

   문제에서 제시되어 있는 그림을 한번 봐보자. 아 보기전에 ! 윗면 아랫면은 계산에서 빼도록 하겠다. 왜그런지는

   밑에서 설명 !

  

   여기서 빨강색 동그라미 친(아마 높이가 4) 부분을 한번 봐보자.

   이 친구의 겉넓이는 몇이 될까?? 아마 10일 것이다.(윗면 아랫면 제외)

   10인 이유는, 저 블록의 왼쪽면 4칸, 뒷면 4칸, 오른쪽면 1칸, 앞면 1칸 해서 10이 될 것이다.

   저 칸수를 계산만 하면 다 더하기만 하면 된다는 말이다.

   칸수는 인접한 칸 블록과의 높이 차이이다.

   오른쪽면을 한번 봐보도록 하자.저 블록의 오른쪽 블록의 높이는 3이기 때문에, 4 - 3 을 해서 총 1칸이

   겉넓이로 계산이 되어진다. 그렇다면 앞면은? 앞면도 똑같이 4 - 3을 해서 총 1칸이 계산되어 진다.

   윗면과 왼쪽면은 드러나있는 면이기 때문에 '4'가 그대로 계산이 되어진다.

   즉 ! 우리는 입력으로 주어지는 높이에서 상하좌우만 비교해서 높이 차만큼만 더해주면 되는 것이다.

   이 때 ! 맵의 범위를 벗어나면 계산을 안해버리면 될까 ??

   아니다. 여기서 맵의 범위를 벗어난다는 것은, 그 쪽 방향에 또 다른 블록이 없다는 것을 의미하고, 그 블록의

   높이만큼 드러나게 된다는 것이다. 즉 , 겉넓이에 포함되어 진다는 의미이다.

   이런식으로 모두 계산을 하면 된다.

   그리고 ! 마지막으로 해줘야 할 것이 앞에서는 계산을 안했떤 윗면과 아랫면이다. 윗면과 아랫면은 왜 계산을

   안했을까?? 무언가와 비교를 할 필요가 없기 때문이다.

   맵의 크기가 3x3이라고 해보자. 그렇다면 겉넓이에 윗면 넓이 9와, 밑면의 넓이 9는 무조건 포함이 된다.

   그 안에 블록이 어떤 모양으로 있던 간에 무조건 포함될 수 밖에 없다.

   따라서 마지막에 더해주기 위해서 빼놓고 계산을 한 것이다.

   중요한 것은 ! 인접한 블록과의 높이차를 이용하면 쉽게 구할 수 있다는 것 !

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Count(int x, int y)
{
    int Cnt = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < N && ny < M)
        {
            if (MAP[nx][ny] < MAP[x][y]) Cnt = Cnt + (MAP[x][y] - MAP[nx][ny]);
        }
        else Cnt = Cnt + MAP[x][y];
    }
    return Cnt;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            Answer = Answer + Count(i, j);
        }
    }
    Answer = Answer + (N * M * 2);
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}