[자바] 백준 9715 - 면적 구하기 (boj java)

문제 : boj9715

 

  이하의 예시를 확인해보자.

2 3
312
103

그림으로 그려보면 아래와 같다.

면적, 즉 다른 상자에 닿아있지 않고 공기(?)와 닿아있는 면의 수를 세면 될 것이다.

 

우선 어떻게 해야 면적을 구할 수 있을지 생각해보자.

 

  우선 가장 간단한 바닥에서 위로 본 형태와, 위에서 바닥쪽으로 본 형태부터 생각해보자. 둘 다 아래와 같이 2차원 평면의 형태로 보일 것이다. 따라서 0이 아닌 위치라면 면은 항상 +2를 해주면 된다(바닥 하나 뚜껑 하나).

 

  그럼 이제 동서남북 4개의 방향에서 공기와 닿아있는 면을 세주면 된다. 우측에서 좌측으로 보는 경우를 한번 생각해보자. 아래 그림과 같은 방향이다.

  설명을 돕기 위해 판이 하나 이동하면서 본다고 해보면, 아래와 같은 두 가지 부분에서 면이 공기와 닿아 있을 것이다.

  주의할 점은 두 번째 이미지에서 진한 파란색 막대의 높이는 3인데, 녹색부분이랑 연결된 부분은 공기와 닿아있지 않으므로 3(진한 파란 높이) - 1(녹색 높이) = 2가 된다는 점이다.

 

  마찬가지로 하나 더 보면, 앞에서 본다면 아래와 같다.

  위와 같이 좌측과 뒤에서 본 모습도 해주면 될 것이다.

 

  즉, r과 c가 있을 때 r을 0부터 증가시키는 방향, r을 0까지 감소시키는 방향, c를 0부터 증가시키는 방향, 0까지 감소시키는 방향을 본다면 동서남북을 다 본 것이고 이 때 이전 높이에 비해 더 커졌다면 커진 만큼이 공기에 닿아있는 면적이 될 것이다. 위의 내용이 이해됬다면 구현자체는 어렵지 않을 것이다.

 

 

코드 : github

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

public class Main {
    private int getArea(int[][] arr, int r, int c) {
        int cnt = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cnt += arr[i][j]>0?1:0;
            }
        }
        cnt*=2;

        for (int i = 0; i < r; i++) {
            int bf = 0;
            for (int j = 0; j < c; j++) {
                if (bf < arr[i][j]) cnt += arr[i][j]-bf;
                bf = arr[i][j];
            }
        }
        for (int i = 0; i < r; i++) {
            int bf = 0;
            for (int j = c-1; j >=0; j--) {
                if (bf < arr[i][j]) cnt += arr[i][j]-bf;
                bf = arr[i][j];
            }
        }
        for (int j = 0; j < c; j++) {
            int bf = 0;
            for (int i = 0; i < r; i++) {
                if (bf < arr[i][j]) cnt += arr[i][j]-bf;
                bf = arr[i][j];
            }
        }
        for (int j = 0; j < c; j++) {
            int bf = 0;
            for (int i = r-1; i >= 0; i--) {
                if (bf < arr[i][j]) cnt += arr[i][j]-bf;
                bf = arr[i][j];
            }
        }
        return cnt;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int[][] arr = new int[r][c];
            for (int i = 0; i < r; i++) {
                String row = br.readLine();
                for (int j = 0; j < c; j++) {
                    arr[i][j] = row.charAt(j)-'0';
                }
            }
            sb.append(getArea(arr, r, c)).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}