백준_2573(DFS & BFS)

DFS와 BFS를 적절히 섞어서 풀면 되는 문제이다.

 

나는 우선 BFS로 빙산이 깎이는 것을 구현하고 매번 빙산이 깎일 때마다 DFS로 빙산이 몇덩어리인지 구했다.

BFS로 빙산 깎는건 간단하니 생략하고

DFS로 빙산 덩어리 구하는건 단순히 DFS로 탐색한 메서드의 호출 횟수와 빙산의 갯수를 비교했다.

 

package TT4_APR;

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 Boj_2573 {
    static int N,M;
    static int map[][];
    static int[][] copy;
    static boolean visited[][];

    static class Point{
        int y;
        int x;

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    static Queue<Point> queue = 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];
        copy = 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());
                if(map[i][j]!=0)
                    queue.offer(new Point(i,j));
            }
        }
        int result =0;

        while(true){
            bergSize = bfs();
            result++;
            Point peek = null;
            if(!queue.isEmpty()) peek = queue.peek();
            if(queue.isEmpty()) break;

            visited = new boolean[N][M];
            visited[peek.y][peek.x]=true;
            level=1;
            dfs(peek.y, peek.x);
            if(level<bergSize) {
               System.out.println(result);
                return;
            }
        }
        System.out.println(0);

        /**
         * 1. BFS로 빙산이 줄어드는것을 구현
         * 2. DFS로 빙산의 덩어리를 구현
         */
    }
    static int[] xp = {1,-1,0,0};
    static int[] yp = {0,0,1,-1};
    static int bergSize;
    static int level;
    private static void dfs(int y,int x) {
        if(level>=bergSize){
            return;
        }
        else{
            for(int i=0;i<4;i++){
                int nx = xp[i] + x;
                int ny = yp[i] + y;
                if(nx >=0 && ny >=0 && nx < M && ny < N && !visited[ny][nx] && map[ny][nx]!=0){
                    visited[ny][nx] = true;
                    level++;
                    dfs(ny,nx);
                }
            }
        }
    }



    private static int bfs() {
        int len = queue.size(); //큐에 들어간 빙산의 정보
        mapcopied(copy,map);

        while(len!=0){
            Point iceBerg = queue.poll();
            int ix = iceBerg.x;
            int iy = iceBerg.y;
            for(int i=0;i<4;i++){
                int nx = xp[i] + ix;
                int ny = yp[i] + iy;
                if(nx >=0 && ny >=0 && nx < M && ny < N && map[ny][nx]==0){
                    if(copy[iy][ix]!=0)
                        copy[iy][ix]--;
                }
            }
            if(copy[iy][ix]!=0) queue.offer(new Point(iy, ix));
            len--;
        }
        mapcopied(map,copy);
        return queue.size();

    }

    private static int[][] mapcopied(int[][] copied,int[][] map) {
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                copied[i][j] = map[i][j];
            }
        }
        return copied;
    }
}