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

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

16931번: 겉넓이 구하기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>


int arr[102][102];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int result = 0;
    result = 2*N*M; //초기값 위아래 겉넓이

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=1; i<=M; i++)
    {
        for(int j=1; j<=N; j++)
        {
            for(int k=0; k<4; k++)
            {
                int nx = i+dx[k];
                int ny = j+dy[k];

                if(arr[j][i] > arr[ny][nx])
                {
                    result += (arr[j][i] - arr[ny][nx]);  //현재값과 다음값의 높이차
                }
            }
        }
    }
    
    cout << result; 

    return 0;
}

윗면 아랫면은 먼저 구하고 시작한다. (2 * N * M)

그러므로 이제 나머지 옆면 4개를 구하면 된다.

현재 값을 중심으로 상하좌우를 탐색하는데 만약 현재 값이 다음 상하좌우 값보다 크다면 현재 값과 다음 값의 높이 차이를 저장한다.

이렇게 구한 높이 차이의 합이 현재 해당 값의 겉넓이다.

 

ex) 높이가 2인 도형 우측에 높이가 1인 도형이 있다면 우측 겉넓이가 1만큼 가려진다. 따라서 높이의 차이인 나머지 1만큼을 우측의 겉넓이로 가지게된다.

이런 방식으로 나머지 상하좌에 대해서도 구한다.