백준 2573. 빙산 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/2573

"BFS"

전체 맵을 탐색하며 빙산이 있는 곳에 상하좌우를 탐색하여 물이 있는 칸의 개수 만큼 빼주는 것은 쉽다. 이때, 유의해야 할점은 같은 시간대에 앞서 녹아버린 빙하가 0이 되면 이 값이 다른 빙하의 감소에 영향을 끼칠 수 있다는 것이다. 이런 부분을 처리하기 위해 감소 시 0 이 되는 빙하는 바로 감소시키는 것이 아니라 값을 그대로 놔두고, 별도 자료구조에 저장해 놓고, 전체 맵을 다 탐색한 이후에 0 이 되는 빙하들을 처리해 주어야 한다. 해당 풀이에서는 별도의 큐를 두어 관리했다. 더해서 또하나 놓치기 쉬운 조건은 빙하 그룹이 0이 되지 못하는 경우이다. 즉, 한 번에 모든 빙하가 다 녹아버리는 경우이다.

이부분은 빙하 감소 시에 감소가 일어났는지 확인하는 boolean 변수를 하나 두어 해결했다.

그렇게 빙하 감소를 거친 후에는 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;
 
class Main {
 
    static int n,m;
    static int[][] map;
    static int[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static Queue<Node> q = new LinkedList<>();
    static Queue<Node> melt = new LinkedList<>();
    
    
    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());
        
        map = new int[n][m];
        visited = new int[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());
            }
        }
        int time = 0;
        
        while(true) {
            if(!melt()) {
                time = 0;
                break;
            }
            
            int mark = 0;
            time ++;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if(map[i][j] == 0 || visited[i][j] == time)
                        continue;
                    mark ++;
                    
                    visited[i][j] = time;
                    q.add(new Node(i, j));
                    
                    while(!q.isEmpty()) {
                        
                        Node cur = q.poll();
                        
                        for (int k = 0; k < 4; k++) {
                            int nx = cur.x + dx[k];
                            int ny = cur.y + dy[k];
                            
                            if(!isRange(nx, ny) || visited[nx][ny] == time || map[nx][ny] == 0)
                                continue;
                            
                            visited[nx][ny] = time;
                            q.add(new Node(nx, ny));
                        }
                        
                    }
                }
            }
            
            if(mark >= 2) break;
        }
        System.out.println(time);
        
    }
    
    static boolean melt() {
        boolean melting = false;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j] == 0) 
                    continue;
                
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    
                    if(isRange(nx, ny) && map[nx][ny] == 0) 
                        cnt++;
                }
                if(cnt > 0) {
                    map[i][j] -= cnt;
                    melting = true;
                }
                
                if(map[i][j] <= 0) { 
                    map[i][j] = 1;
                    melt.add(new Node(i, j));                    
                }
            }
        }
        
        while(!melt.isEmpty()) {
            Node node = melt.poll();
            map[node.x][node.y] = 0;
        }
        
        return melting;
    }
    
    static boolean isRange(int x, int y) {
        if ( x < 0 || x >= n || y < 0 || y >= m) return false;
        return true;
    }
 
}
 
class Node {
    int x ;
    int y ;
    
    Node(int x , int y) {
        this.x = x;
        this.y = y;
    }
}