[Gold IV] 빙산 - 2573 (Java)

문제 요약

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다.

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오.  만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

---

문제 분석

빙산의 위치를 큐에 저장하고 큐에서 빙산의 위치를 빼네 주변 바다의 개수만큼 뺴주기
그 후 한 빙산의 위치에서 bfs를 돌려 탐색한 개수가 큐사이즈와 같은지 확인

만약 사이즈가 다르다면 빙산은 두 개 이상으로 갈라진 것

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int N, M;

    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());
        // 빙산의 위치를 저장한 큐
        Queue<Point> iceQ = new LinkedList<>();
        int[][] map = new int[N][M];
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            for (int m = 0; m < M; m++) {
                map[n][m] = Integer.parseInt(st.nextToken());
                if (map[n][m] != 0) {
                    iceQ.add(new Point(n, m));
                }
            }
        }
        // 정답
        int answer = 1;
        while (!iceQ.isEmpty()) {
            int[][] tempMap = deepClone(map);
            // 빙산 녹이기
            int qSize = iceQ.size();
            for (int i = 0; i < qSize; i++) {
                Point p = iceQ.poll();
                for(int d = 0; d < 4; d++){
                    if(tempMap[p.r+dr[d]][p.c+dc[d]] == 0){
                        map[p.r][p.c]--;
                    }
                }
                if(map[p.r][p.c]<0){
                    map[p.r][p.c] = 0;
                }
                if (map[p.r][p.c] != 0) {
                    iceQ.add(p);
                }
            }

            // 빙산 개수 확인하기
            boolean[][] visited = new boolean[N][M];
            int icebergCount = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0 && !visited[i][j]) {
                        bfs(i, j, map, visited);
                        icebergCount++;
                    }
                }
            }
            // 빙산이 두 덩어리 이상으로 분리되었으면 결과 출력
            if (icebergCount >= 2) {
                break;
            }
            answer++;
//            System.out.println();
//            for(int[] a : map){
//                System.out.println(Arrays.toString(a));
//            }
        }
        if(iceQ.isEmpty()){
            answer = 0;
        }
        System.out.println(answer);
    }

    private static void bfs(int row, int col, int[][] map, boolean[][] visited) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(row, col));
        visited[row][col] = true;

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];
                if (isArrOut(nr, nc) || map[nr][nc] == 0 || visited[nr][nc]) {
                    continue;
                }
                queue.add(new Point(nr, nc));
                visited[nr][nc] = true;
            }
        }
    }

    private static boolean isArrOut(int nr, int nc) {
        return nr < 0 || nc < 0 || nr >= N || nc >= M;
    }
    private  static int[][] deepClone(int[][] map){
        int[][] temp = new int[N][M];
        for(int n = 0; n < N; n++){
            temp[n] = map[n].clone();
        }
        return temp;
    }
}

---

정리

새로 배운 내용

없음

개선할 점

없음

더 찾아볼만한 사항

없음

---