문제

BOJ 16931: 겉넓이 구하기 https://www.acmicpc.net/problem/16931

풀이

조건

• 입력 받은 N X M 크기의 값들은 각각 그 위치에 있는 정육면체의 높이이다.
• 겉넓이를 모두 구하면 된다.

풀이 순서

• 겉넓이 구하는 방법
  1. 맨 앞의 면은 겉넓이에 그냥 더한다.
  2. 바로 뒷 쪽의 높이에서 앞 쪽의 높이를 뺀다.
  • 이 때 뺀 값이 양수일 때만 겉넓이에 더한다.
  3. 1, 2 번의 방식대로 동, 서, 남, 북 방향에서 수행하고 윗쪽, 아랫쪽은 그냥 면적의 넓이를 더한다.

예를 들면

• 노란색 방향의 1번 방향 겉넓이 구하기
  1. 맨 앞의 면은 겉넓이에 그냥 더한다. ===> 파란색 숫자 1번 면적
  2. 바로 뒷 쪽의 높이에서 앞 쪽의 높이를 뺀다.
     • ===> 뒷쪽의 높이(3) - 앞쪽의 높이(1) = 2
     • 파란색 2번, 3번 면적
  3. 마지막까지 반복한다.
  4. 노란색 방향의 1번 방향 총 겉넓이 = 4
• 빨간색 방향의 3번 방향 겉넓이 구하기
  1. 맨 앞의 면은 겉넓이에 그냥 더한다. ===> 녹색 숫자 1, 2, 3, 4번 면적
  2. 바로 뒷 쪽의 높이에서 앞 쪽의 높이를 뺀다.
  • 이 때 뺀 값이 양수일 때만 겉넓이에 더한다.
    • ===> 뒷쪽의 높이(3) - 앞쪽의 높이(4) = -1
    • 이 땐 뺀 값이 음수가 나왔으므로 총 겉넓이에 더하지 않는다.
  • 마지막 높이(5) - 마지막에서 바로 앞 높이(4) = 1 ===> 녹색 숫자 5번 면적
    • ===> 이 때는 뺀 값이 양수가 나왔으므로 총 겉넓이에 더한다.
  3. 빨간색 방향의 3번 방향 총 겉넓이 = 5

코드

import java.util.*;
import java.io.*;

public class Main {
    
	static int N, M;
	static int[][] map;
	
    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());
    	
    	map = new int[N][M];
    	
    	int sum = 0; // 겉넓이
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=0; j<M; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    			if(map[i][j] != 0) {
    				sum++;
    			}
    		}
    	}
    	
    	sum *= 2; // 아래에서 바라본 방향, 위에서 바라본 방향은 그냥 더해주면 됨
    	
    	//동 쪽에서 바라봄
    	for(int i=0; i<N; i++) {
    		for(int j=M-1; j>=1; j--) {
    			int space = map[i][j-1] - map[i][j]; // 바로 뒷 칸의 높이에서 앞 칸의 높이를 빼면 겉넓이가 된다.
    			if(space >= 0) { // 겉넓이가 양수일 때만 총 겉넓이에 더해주면 된다.
    				sum += space;
    			}
    		}
    		sum += map[i][M-1]; // 가장 앞쪽에 있는 면은 그냥 더해주면 된다.
    	}
    	
    	//서 쪽에서 바라봄
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<=M-2; j++) {
    			int space = map[i][j+1] - map[i][j];
    			if(space >= 0) {
    				sum += space;
    			}
    		}
    		sum += map[i][0];
    	}
    	
    	//남 쪽에서 바라봄
    	for(int j=0; j<M; j++) {
    		for(int i=N-1; i>=1; i--) {
    			int space = map[i-1][j] - map[i][j];
    			if(space >= 0) {
    				sum += space;
    			}
    		}
    		sum += map[N-1][j];
    	}
    	
    	//북 쪽에서 바라봄
    	for(int j=0; j<M; j++) {
    		for(int i=0; i<=N-2; i++) {
    			int space = map[i+1][j] - map[i][j];
    			if(space >= 0) {
    				sum += space;
    			}
    		}
    		sum += map[0][j];
    	}
    	
    	System.out.println(sum);
    }
	
}

정리

• 겉넓이 구하는 방법을 차례로 생각하며 풀면 쉽게 풀린다.