16931 겉넓이 구하기

https://www.acmicpc.net/problem/16931

16931번: 겉넓이 구하기

---

생각한 과정

만들어진 정육면체 더미를 한 쪽 면만 보이게 바라보면 어떻게 쌓여있든지 그 쪽 면의 넓이를 간단히 구할 수 있다고 생각했다.

 

그런데 이 방법은 틀렸다. 

출처 : 백준 문제

이 더미를 짙은 주황색면만 보이도록 바라보았을 때 뒷편에 가려지는 겉넓이가 있다. 단면만 바라보면 안된다는걸 깨닫고, 각 층마다 옆 블록이 인접했는지 따져 겉넓이를 구하기로 했다. 

 

어떤 상황에서든지 윗면과 아랫면은 각각 N*M개가 생긴다. 따라서 각 블록의 옆면이 몇 개인지 세어보면 된다.

 

한 블록에 다른 블록이 인접하면 겉넓이가 생기지 않는다. 따라서 어떤 블록의 특정 층보다 인접한 층의 높이가 낮은 경우만 겉넓이가 생긴다.

int arr[102][102];

// input...

for(int floor=0; floor<100; ++floor){
  for(int i=1; i<=N; i++){
    for(int j=1; j<=M; j++){
      res += 4 - (
        (arr[i][j] > arr[i-1][j]) + 
        (arr[i][j] > arr[i][j-1]) + 
        (arr[i][j] > arr[i][j+1]) + 
        (arr[i][j] > arr[i+1][j]));
    } 
  }
}

이렇게 해도 답이 된다. 하지만 N과 M이 100일 경우 100*100*100번 반복을 돌게 된다. 따라서 각 좌표의 높이만큼만 돌게 하면 더 좋다.

int arr[102][102];

// input...


for(int i=1; i<=N; i++){
  for(int j=1; j<=M; j++){
    for(int floor=0; floor<arr[i][j]; ++floor){
      res += 4 - (
        (arr[i-1][j] > floor) + 
        (arr[i][j-1] > floor) + 
        (arr[i][j+1] > floor) + 
        (arr[i+1][j] > floor));
    } 
  }
}

미흡했던 점

계속 예제도 다 통과하고 맞는 알고리즘 같은데, 자꾸 틀린다. 이유는 정말 간단해서 말하기 부끄러울 정도다.

 

vscode에서 실행할 때는 배열 초기화를 하지 않아도 원소들을 전부 0으로 초기화한다. 하지만 백준에서는 그렇지 않았다.

 

쓰레기값으로 계속 연산하려고 하니 뭘 해보지도 못하고 틀렸습니다! 가 나오더라... 다시는 이러지 말자.

---

#include <iostream>
int main() {
  int N, M, map[102][102]{0};
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      scanf("%d", &map[i][j]);
    }
  }
  int res = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      for (int floor = 0; map[i][j] > floor; floor++) {
        res += 4 - ((map[i - 1][j] > floor) + (map[i][j - 1] > floor) +
                    (map[i][j + 1] > floor) + (map[i + 1][j] > floor));
      }
    }
  }
  printf("%d", res + N * M * 2);
}

---

조금 더 머리를 썼을 때 2중for문으로도 문제를 해결할 수 있다.

 

어떤 좌표(A)에 쌓여있는 블록들의 겉넓이는 인접한 좌표(B)의 높이에 따라 결정된다.

 

직전에 말한 어떤 좌표의 특정 층의 높이보다 인접한 좌표의 높이가 낮아야지만 겉넓이가 생긴다고 했다. 

 

따라서 어떤 좌표의 높이와 인접한 좌표의 높이를 뺀 값은 노출되는 겉넓이의 개수를 의미한다.

 

높이가 5인 블록과 높이가 3인 블록이 인접해있다고 하자. 높이가 5인 블록은 5-3=2개의 면이 노출되어 있다.

그렇지만 반대로 높이가 3인 블록은 노출되는 면이 없다. 따라서 인접한 블록의 높이가 더 작은 경우에만 계산한다.

 

다행히도 문제에서 정육면체의 단위를 1*1*1로 지정해주었기 때문에 높이에 관해 별다른 연산을 하지 않아도 된다.

---

#include <iostream>
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
int main() {
  int N, M, map[102][102]{0};
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      scanf("%d", &map[i][j]);
    }
  }
  int res = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      res += MAX(0, map[i][j] - map[i - 1][j]) +
             MAX(0, map[i][j] - map[i][j - 1]) +
             MAX(0, map[i][j] - map[i][j + 1]) +
             MAX(0, map[i][j] - map[i + 1][j]);
    }
  }
  printf("%d", res + N * M * 2);
}