[백준] 2573번 : 빙산

2573번: 빙산

---

[BFS or DFS] (BFS(위)에 비해 DFS(아래) 코드가 좀 더 간결하고 메모리와 시간 효율도 더 좋았다.)

문제의 난이도는 크게 어렵지 않았다. 2중 루프가 많이 사용되었다. 그래서 시간과 메모리에 민감한 문제였던 것 같다. 함수 내에서 빙산이 2부분으로 쪼개지는 시점의 time을 반환해야하고, 만약 빙산이 다 녹을 때 까지 2부분으로 나누어지지 않으면 0을 반환하는 문제이다.

 

처음 2차원 배열을 입력받는 map[][]과 map[i][j]의 주변의 바다(0)의 개수를 저장하는 sea[][]를 가지고 계속 빼주면서 while()의 base case를 만날 때 까지 DFS든 BFS든 이용해주면 된다.

 

코드의 길이가 길긴 하지만 구성은 간단하므로 실행 흐름대로 보면 금방 이해할 수 있다.

# DFS Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }
    
    static Queue<Point> Q = new LinkedList<>();
    
    static int[] Y = {0, 0, 1, -1}, X = {1, -1, 0, 0};
    static int[][] map = new int[301][301], sea = new int[301][301];
    static boolean[][] visit;
    
    static int n, m, time = 0, cnt;

    //map[i][j]의 주변 바다의 개수 반환
    static int getSea(int i, int j){
        int sea = 0;
        for (int a = 0; a < 4; a++) {
            int ny = i + Y[a];
            int nx = j + X[a];

            if (map[ny][nx] == 0)
                sea++;
        }
        return sea;
    }

    static void DFS(int y, int x){

        visit[y][x] = true;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(!visit[ny][nx] && map[ny][nx] > 0)
                DFS(ny,nx);
        }
    }

    static int func(){
        while(true){
            boolean flag = false;
            visit = new boolean[301][301];
            cnt = 0;

            //시간을 증가시키고 map = map - sea
            time++;

            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++)
                    if(map[i][j] > 0) sea[i][j] = getSea(i,j);

            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++)
                    if(map[i][j] > 0) {
                        flag = true;

                        if (map[i][j] - sea[i][j] > 0)
                            map[i][j] -= sea[i][j];
                        else
                            map[i][j] = 0;
                    }
            if(!flag) break; //flag == false 이면 얼음이 모두 녹은 것

            //빙산이 나누어졌는지 cnt 계산(DFS)
            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++)
                    if(!visit[i][j] && map[i][j] > 0){
                        cnt++;
                        if(cnt >= 2) return time;
                        DFS(i, j);
                    }

        }//.while
        return 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());

        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());
        }

        System.out.println(func());
    }
}

# BFS Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }
    
    static Queue<Point> Q = new LinkedList<>();
    
    static int[] Y = {0, 0, 1, -1}, X = {1, -1, 0, 0};
    static int[][] map = new int[301][301], sea = new int[301][301];
    static boolean[][] visit;
    
    static int n, m, time = 0, cnt;

    //map[i][j]의 주변 바다의 개수 반환
    static int getSea(int i, int j){
        int sea = 0;
        for (int a = 0; a < 4; a++) {
            int ny = i + Y[a];
            int nx = j + X[a];

            if (map[ny][nx] == 0)
                sea++;
        }
        return sea;
    }

    static int func(){
        while(true){
            boolean flag = false;
            visit = new boolean[301][301];
            cnt = 0;

            //시간을 증가시키고 map = map - sea
            time++;

            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++)
                    if(map[i][j] > 0) sea[i][j] = getSea(i,j);

            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++)
                    if(map[i][j] > 0) {
                        flag = true;

                        if (map[i][j] - sea[i][j] > 0)
                            map[i][j] -= sea[i][j];
                        else
                            map[i][j] = 0;
                    }
            if(!flag) break; //flag == false 이면 얼음이 모두 녹은 것

            //빙산이 나누어졌는지 cnt 계산(BFS)
            for(int i=1; i<n-1; i++)
                for(int j=1; j<m-1; j++){
                    if(!visit[i][j] && map[i][j] > 0){
                        cnt++;
                        if(cnt >= 2) return time;

                        visit[i][j] = true;
                        Q.add(new Point(i, j));
                    }

                    while(!Q.isEmpty()){
                        Point p = Q.poll();
                        int y = p.y;
                        int x = p.x;

                        for(int a=0; a<4; a++){
                            int ny = y+Y[a];
                            int nx = x+X[a];

                            if(!visit[ny][nx] && map[ny][nx] > 0){
                                visit[ny][nx] = true;
                                Q.add(new Point(ny, nx));
                            }
                        }
                    }
                } //.BFS
        }//.while
        return 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());

        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());
        }

        System.out.println(func());
    }
}