[백준]2573: 빙산 - JAVA

[백준]2573: 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

풀이

탐색을 하면서 빙산의 개수를 세고, 탐색을 하면서 빙하를 녹이는 문제이다. 

빙산의 개수가 2개 이상이되는 순간 탐색을 멈추고 그 때의 year값을 반환한다. 빙산의 개수가 0이되버리면 2개 이상이 될 수 없으므로 0을 반환한다.

 

빙하가 녹을때 주의해야 할 점이 있다. 아래와 같은 경우이다.

0	0	0
0	2 -> 0	5
0	0	0

이때 가운데 칸의 빙하가 녹고 나면 2에서 0으로 변경 될 것이다. 왜냐하면 주변에 바다(0인 노드의 수)의 개수가 3이고 2에서 3을 뺀 값은 0보다 작기 때문에 0으로 생각해준다.

 

그리고 그 다음칸에서 주변의 바다 수를 세면 3이된다. 2 -> 원래 빙하가 있었던 자리인데도 불구하고 0으로 변경되었기 때문에 바다라고 세 주는 것이다. 이러한 상황을 방지해 주기 위해 boolean배열을 선언해 주었다. 이미 빙하가 있었던 자리는 true로 표시해 0이되더라도 카운트 되지 않도록 처리해 주었다.

위의 과정은 빙하가 있는 노드를 시작으로 순차적으로 이루어 져야 하기 때문에 bfs로 탐색해 주었다. 

 

빙산의 개수를 세는 부분은 dfs를 사용해서 구현하였다. 

코드

import java.util.*;
 
public class Main {    
 
    static int n, m;
    static int[][] board;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        board = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        int year = 0;
        while(true) {
            int iceburge = countIceburge(); //빙산의 개수를 센다
            if(iceburge >= 2) break; 
            else if(iceburge == 0) {
                year = 0;
                break;
            }
            melting(); //빙하가 녹는다
            year++;
        }
        
        System.out.println(year);
    }
    
    public static void melting() {
        Queue<int[]> q = new LinkedList<>();
        
        boolean[][] memo = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] != 0) {
                    q.offer(new int[] {i, j});
                    memo[i][j] = true;
                }
            }
        }
        
        while(!q.isEmpty()) {
            int count = 0;
            int[] node = q.poll();
            
            //주변 4방향의 바다에 해당되는 칸의 수를 센다.
            for(int i = 0; i < 4; i++) {
                int nx = node[0] + dx[i];
                int ny = node[1] + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(!memo[nx][ny] && board[nx][ny] == 0) count++;
                }
            }
            if(board[node[0]][node[1]] < count) board[node[0]][node[1]] = 0;
            else board[node[0]][node[1]] -= count;
            
        }
    }
    
    public static int countIceburge() {
        int count = 0;
        boolean[][] visited = new boolean[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] != 0 && !visited[i][j]) {
                    dfs(i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }
    
    public static void dfs(int x, int y, boolean[][] visited) {
        visited[x][y] = true;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if(board[nx][ny] != 0 && !visited[nx][ny]) {
                    dfs(nx, ny, visited);
                }
            }
        }
    }
}