#백준_2573 빙산 - Java 자바

# 유형 : BFS

# 빙산 녹는 처리를 해주는 BFS, 연결성 체크를 위한 BFS  2가지를 구현하면 된다. 백준 7569, 3055 문제도 탐색을 두번하는 문제였는데, 풀어봤다면 어떻게 접근할지 보이는 문제라고 생각한다. 

 

# 구현

1. 빙산인 부분을 리스트에 저장

2. 리스트에 저장된 빙산의 좌표를 큐에 넣고, 큐의 사이즈 만큼 좌표의 4방향중 0인 곳인 만큼 값을 빼준다. 

3. 값을 빼주는 작업이 끝날 때마다 연결성을 체크하여 2개이상으로 분리되는지 체크한다.

4. 빙산이 다 녹을때까지 분리가 안된다면 0을 출력한다.

5. 예외케이스로 입력부터 두 개이상으로 분리되는 경우가 있다. 이를 처리해줘야 한다.

 

추가적인 테스트케이스

https://www.acmicpc.net/board/view/19033

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2573 {
    static int result=0;
    static int N,M;
    static int arr[][],map[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Point> arrList = new ArrayList<>();
    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());
        arr = new int[N][M];
        map = new int[N][M];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                int val = Integer.parseInt(st.nextToken());
                arr[i][j] = val;
                map[i][j] = val;
                if(val != 0)
                    arrList.add(new Point(j,i));
            }
        }
        if(check(arrList.get(0)) != arrList.size())
            System.out.println(0);
        else
            bfs();
    }
    
    public static void bfs() {
        Queue<Point> queue = new LinkedList<Point>();
        
        for(int k=0; k<arrList.size(); k++) {
            Point p = arrList.get(k);
            queue.add(p);
        }
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            result++;
            for(int s=0; s<size; s++) {
                Point p = queue.poll();
                int count = 0;
                for(int d=0; d<4; d++) {
                    int newX = p.x + moveX[d];
                    int newY = p.y + moveY[d];
                    if(0<=newX && newX<M && 0<=newY && newY<N && arr[newY][newX]==0)
                        count++;
                }
                if(count >= map[p.y][p.x])
                    map[p.y][p.x] = 0;
                else {
                    map[p.y][p.x]-=count;
                    queue.add(p);
                }
            }
            for(int q=0; q<N; q++) {
                for(int w=0; w<M; w++) {
                    arr[q][w] = map[q][w];
                }
            }
            if(queue.peek()!=null && check(queue.peek()) != queue.size()) {
                System.out.println(result);
                return;
            }
        }
        System.out.println(0);
    }
    
    //연결 체크
    public static int check(Point p) {
        int count = 0;
        boolean visit[][] = new boolean[N][M];
        Queue<Point> queue = new LinkedList<>();
        queue.add(p);
        visit[p.y][p.x] = true;
        while(!queue.isEmpty()) {
            Point tmp = queue.poll();
            count++;
            for(int d=0; d<4; d++) {
                int newY = tmp.y + moveY[d];
                int newX = tmp.x + moveX[d];
                if(0<=newY && newY<N && 0<=newX && newX<M ) {
                    if(arr[newY][newX]!=0 && !visit[newY][newX]) {
                        visit[newY][newX]=true;
                        queue.add(new Point(newX,newY));
                    }
                }
            }
        }
        return count;
    }
}