[BOJ 16931] 겉넓이 구하기 (Java)

BOJ 16931 겉넓이 구하기

문제풀이

굉장히 재밌는 문제다. 간단하면서 아이디어를 가지고 푸는 문제는 퀴즈를 푸는 것 처럼 재밌다. 구현 때문에 힘든일도 없고...

이 문제는 구조적으로 나눠서 단순화 시키는 것이 핵심이다.

• 위, 아래의 면은 가리는 것이 없기 때문에 N M 2 다.
• 옆면은 사방의 블록들의 높이에 따라서 가리는 면을 고려해야한다.
  • 기본적으로 블록의 옆면은 4개 이므로 4 * 높이다. 여기서 사방 탐색하며 옆면에 가리는 부분을 빼주면 된다.
    • 높이가 더 높을 때
      주위 블록의 높이가 더 높을 때 가리는 면은 현재 블록의 높이와 같다.
    • 높이가 낮거나 같을 때
      주위 블록의 높이가 낮거나 같을 때 가리는 면은 주위 블록의 높이와 같다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] map;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int N, M, ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		ans = 0;
		
		map = new int[N][M];
		
		for(int r = 0 ; r < N ; ++r) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0 ; c < M ; ++c) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 위, 아래
		ans += N * M * 2;
		
        // 옆
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				int cnt = map[r][c] * 4;
				
				for(int d = 0 ; d < 4 ; ++d) {
					int nr = r + dir[d][0];
					int nc = c + dir[d][1];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

					if(map[nr][nc] > map[r][c]) {
						cnt -= map[r][c];
					} else {
						cnt -= map[nr][nc];
					}
				}
				
				ans += cnt;
			}
		}
		
		System.out.println(ans);
	}
}