[BOJ]2573 - 빙산(G4)

문제 링크

2573-빙산

입력

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

출력

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

문제 풀이

단순한 문제였지만 dfs 와 bfs를 함께 이용한다는 점에서 헤맬 수 있는 문제였다.

빙산이 한 덩어리 일 경우에는 빙하를 녹이고
두 덩어리 이상이라면, 빙하를 그만 녹이고 cnt를 출력
두 덩어리가 되기 전에 빙하가 전부 녹아버린다면 0을 출력과 같은 로직이다.

분리된 빙하의 갯수를 구하기 위한 getCnt 함수는 dfs 를 이용
아직 빙하가 한 덩어리라면, 빙하를 녹이기 위한 melt함수는 bfs 를 이용

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

public class Main {
    static int N, M;
    static int[][] maps;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    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());
        
        maps = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0, cnt = 0;
        while ((cnt = getCnt()) < 2) {
        	// 빙하가 두개로 나뉘기 전에 다 녹는 경우
            if (cnt == 0) {
                result = 0;
                break;
            }
            melt();
            result++;
        }
        System.out.println(result);
    }

    public static int getCnt() {
        visited = new boolean[N][M];

        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maps[i][j] != 0 && !visited[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(maps[nx][ny]!= 0&& !visited[nx][ny]) dfs(nx, ny);
        }
    }

    public static void melt(){
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maps[i][j] != 0) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int zeroCnt = 0;

            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
                if (!visited[nx][ny] && maps[nx][ny] == 0) zeroCnt++;
            }

            if (maps[cur[0]][cur[1]] - zeroCnt < 0) maps[cur[0]][cur[1]] = 0;
            else maps[cur[0]][cur[1]] -= zeroCnt;
        }
    }
}