[Algorithm] 백준 16931번_겉넓이 구하기(Java)

1. 16931번 겉넓이 구하기

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

16931번: 겉넓이 구하기

2. 문제

---

크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다.

종이의 각 칸에 놓인 정육면체의 개수가 주어졌을 때, 이 도형의 겉넓이를 구하는 프로그램을 작성하시오.

위의 그림은 3×3 크기의 종이 위에 정육면체를 놓은 것이고, 겉넓이는 60이다.

3.  

4. 입력

---

첫째 줄에 종이의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 종이의 각 칸에 놓인 정육면체의 수가 주어진다.

 

5. 출력

---

첫째 줄에 도형의 겉넓이를 출력한다.

 

6. 제한

---

• 1 ≤ N, M ≤ 100
• 1 ≤ 종이의 한 칸에 놓인 정육면체의 수 ≤ 100

7.  

8. 알고리즘

---

사방탐색이란 ? 사방탐색 배열을 생성해서 현재 위치에서  상 하 좌 우를 탐색하는 방법.

 

<방법>

1. 동서남북을 좌표로 나타내면, (-1, 0), (0, 1),(1, 0),(0, -1)이므로 dx, dy 배열을 만들어준다.

      

      

      

    
    

      <java />
    
int [] dx = {-1, 0, 1, 0}
int [] dy = {0, 1, 0, -1}

 

2. 사용방법 : 반복문 안에 dx, dy 위치를 바꿔가면서 탐색.

                 주의할 점 : 배열 크기 밖에 있는 것들은 탐색할 필요가 없으므로 if 문으로 넘겨주어야 한다.

      

      

      

    
    

      <java />
    
//현재위치를 x, y, 배열 크기 : N X M 이라고 가정
for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1) continue;
}

 

예시 그림의 사각형 개수를 행렬로 나타낸 표

위의 그림처럼 현재 위치가 1이면, 1 주변의 상 하 좌 우를 탐색하면서 결과를 도출하는 방법이다.

이 문제는 사방탐색으로 생각했을 때 경우의 수는 2가지이다.

1. 범위 밖으로 벗어난 경우 : 결과 += 현재위치

2. 현재 위치 > 비교하는 위치 : 결과 += 현재위치 - 비교하는 위치

 

9. 코드

---

      

      

      

    
    

      <java />
    
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int[] dx = {-1, 0 , 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] cube = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                cube[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        answer += 2 * N * M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < 4; k++) { //사방 탐색
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1) { //비교대상이 없으면
                        answer += cube[i][j]; //현재 사각형 개수를 더해준다.
                        continue;
                    }
                    if(cube[nx][ny] < cube[i][j]) { // 비교 대상 < 현재위치 
                        answer += cube[i][j] - cube[nx][ny];
                    }
                }
            }
        }
        sb.append(answer).append("\n");
        System.out.println(sb);
    }
}