[BOJ_16931] 겉넓이 구하기 (java)

문제링크

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

16931번: 겉넓이 구하기

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 시뮬레이션, 구현

출처 - BOJ

겉넓이를 모두 구해주는 문제이다. 윗면과 아랫면 그리고 옆면으로 나누어 구현을 해주면 된다.

 

1. 윗면과 아랫면
   윗면과 아랫면의 겉넓이를 구하는 방법은 매우 간단하다. 조건에서 주어진 $n*m$에 블럭이 1개 이상 들어가야하므로 항상 넓이는 $n*m$이 된다.
   
   
2. 옆면
   옆면의 넓이를 구하는 방법은 4방면으로 붙어있는 도형을 확인하는 것이다. 옆에 있는 도형보다 높게 쌓여진 경우 겉넓이가 보여지게 된다. 이때 겉넓이는 두 도형의 높이의 차이만큼 보여지게 된다. 따라서 4방면을 확인하여 만약 옆에 도형보다 높게 쌓여진 경우라면 그 전 도형과 차이를 넓이에 추가해주면 해결할 수 있다. 그리고 맨 끝쪽 부분은 도형이 0개이기 때문에 해당 도형의 높이만큼 겉넓이를 추가해주면 쉽게 해결할 수 있다.

구현코드

package boj_16931;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] paper = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                paper[i][j] = sc.nextInt();
            }
        }

        int area = n * m * 2; //밑, 윗 넓이
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i - 1 < 0) {
                    area += paper[i][j];
                } else {
                    if (paper[i - 1][j] < paper[i][j])
                        area += paper[i][j] - paper[i - 1][j];
                }

                if (i + 1 >= n) {
                    area += paper[i][j];
                } else {
                    if (paper[i + 1][j] < paper[i][j])
                        area += paper[i][j] - paper[i + 1][j];
                }

                if (j - 1 < 0) {
                    area += paper[i][j];
                } else {
                    if (paper[i][j - 1] < paper[i][j])
                        area += paper[i][j] - paper[i][j - 1];
                }

                if (j + 1 >= m) {
                    area += paper[i][j];
                } else {
                    if (paper[i][j + 1] < paper[i][j])
                        area += paper[i][j] - paper[i][j + 1];
                }
            }
        }
        System.out.println(area);
    }
}

 

시간복잡도

시간 복잡도는 주어진 n*m공간에 대하여 4방면을 확인하기 때문에 $O(n*m)$이 된다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)