[백준] 2573번 - 빙산 (java)

Baekjoon 2573 - 빙산 (클릭 시 이동)

문제

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


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


2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다.


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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	38110	10724	7021	25.731%

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

풀이

1. 입력이 모두 0일 경우를 고려한다.
2. (1)의 경우가 아니라면 무조건 한 덩어리가 입력으로 주어지므로 모든 배열을 돌며 각 얼음을 녹일 갯수를 세어 저장한다.
3. 다시 한번 더 돌며 빙산을 녹여 없앤다.
4. bfs를 수행하여 빙산의 갯수를 세고 하나의 빙산이라면 (2)부터 다시 수행한다.
5. 만약 bfs를 수행하지 못한다면 0을 출력한다.(모두 녹아 없어진 경우)

과정

1. 입력이 모두 0일경우 && BFS

입력으로 빙산이 없는 경우가 주어지는것과 모두 녹아 없어진 경우는 같은 로직으로 해결할 수 있다.

입력이 모두 0이면 입력받을 때 0보다 큰 입력값의 갯수를 세면 되긴 하지만

어차피 bfs를 구현해야하므로 대체했다.

int count = 0;

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] > 0 && !visited[i][j]) {    // 얼음을 만나면 bfs 수행
            bfs(i, j);
            count++;            // 수행한 횟수를 센다(빙산의 갯수)
        }
    }
}
if (count > 1)            //빙산이 2개 이상일 경우.
    break;
else if (count == 0) {    // 모두 녹아 없어진 경우.
    answer = 0;
    break;
}

2. 빙산 녹이기

그냥 모든 배열을 돌며 녹일 양을 저장하고 모두 탐색했다면 다시 모든 배열을 돌며 녹인다.

7번라인에 map[nr][nc] 가 1보다 작을 때인 이유는 얼음의 양이 1이고 주변의 바다(0)가 3개라면 음수값이 나온다.

(0 이하는 모두 바다로 판단하게끔 로직을 구현했기 때문)

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] > 0) {
            for (int step = 0; step < 4; step++) {
                int nr = i + deltas[step][0];
                int nc = j + deltas[step][1];
                if (isIn(nr, nc) && map[nr][nc] < 1) {    
                    melt[i][j]++;
                }
            }
        }

    }
}

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        map[i][j] -= melt[i][j];
    }
}


answer++;        // 빙산을 녹이는데 걸린 시간(년)

최종 소스코드

package BJ_Practice;

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

public class BJ_G4_2573_빙산 {
    static int N, M;
    static int answer = 0;
    static int[][] map;
    static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static boolean[][] visited;
    static StringTokenizer st;

    static class Position {
        int r, c;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        int melt[][] = new int[N][M];
        visited = new boolean[N][M];

        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());
            }
        }

        while (true) {
            for (int i = 0; i < N; i++) {
                Arrays.fill(visited[i], false);
                Arrays.fill(melt[i], 0);
            }

            int count = 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);
                        count++;
                    }
                }
            }
            if (count > 1)
                break;
            else if (count == 0) {
                answer = 0;
                break;
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        for (int step = 0; step < 4; step++) {
                            int nr = i + deltas[step][0];
                            int nc = j + deltas[step][1];
                            if (isIn(nr, nc) && map[nr][nc] < 1) {
                                melt[i][j]++;
                            }
                        }
                    }

                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map[i][j] -= melt[i][j];
                }
            }
            answer++;
        }

        System.out.println(answer);

    }

    static void bfs(int r, int c) {
        Queue<Position> queue = new LinkedList<>();
        queue.offer(new Position(r, c));
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            Position temp = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nr = temp.r + deltas[i][0];
                int nc = temp.c + deltas[i][1];

                if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] > 0) {
                    queue.offer(new Position(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}