백준 2573 빙산 java

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

 

한덩어리로 뭉쳐져있는(dfs로 한번에 탐색 가능한) 빙산이 입력되고, 그것이 두덩이 이상으로 쪼개질 때를 감지해야한다.

 

풀이1

내가 푼 방식

입력받으면서 빙하인 부분을 큐에 담는다.

1년 진행마다 기존 빙하와 바다 상태(arr)의 정보를 복사한다(copied)

큐에서 poll하며 빙하가 있던 곳의 위치를 기반으로 copied에 있는 빙하를 녹인다.

(복사해서 하는 이유는, 원래 arr에서 순차적으로 녹일 경우, 원래는 빙하였던 자리가 바다가 되면

덜 녹아야 하는 다음 빙하가 더 녹게 되는 경우가 생겨 결과가 바뀔 수 있다.)

1년치 녹고도 바다가 되지 않은 빙하는 다시 큐에 담아준다.

1년치 모두 녹이고 난 뒤에 dfs를 돌고 dfs로 visited되지 않은 곳에 있는 빙하가 q 속에 있다면(iterator로 큐 순회)

갈라진 것이므로 감지해낸다.

 

풀이2

빙하를 녹이는 방식을 메모리를 절약해서 할 수 있다.

일단 arr을 다 훑으며 빙산이 있으면 큐에 넣고 visited 처리를 해준다.

그리고 큐를 모두 poll 하며 주변이 배열을 벗어나지 않고 visited되어있지 않은 수를 찾아서 그만큼 녹인다.

 

풀이1의 코드

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    /*
    동시에 녹는거다. 순차절으로 녹으면 옆에 영향이가서 결과가 바뀐다.
    복사본을 만들고, 큐에 들어가있는 좌표로 원본의 주변 정보 기준으로 복사본을 업데이트한다.
    0으로 바뀌면 그대로 poll만 하고 그래도 값이 남아 있으면 업데이트 된 값으로 q에 넣고
    다끝난 다음에 원본을 다시 업데이트한다.
    맨 사이드는 0으로 채워지니까 그냥 주변 다 검사해도 문제없을듯
    한번 돌고나서 원본 놓고 dfs돌았는데 q 다 체크 안되면 두덩이 쪼개진거니까 거기체크.
    q 빌때까지 한덩이면 0을 출력하자.(기본값을 0으로 둬)
     */
    static int rowsize, colsize;

    static class point {
        public int row;
        public int col;

        public point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static void copyFunc(int mode) {
        if (mode == 1) {
            for (int i = 0; i < rowsize; i++) {
                for (int j = 0; j < colsize; j++) {
                    copied[i][j] = arr[i][j];
                }
            }
        }
        else{
            for (int i = 0; i < rowsize; i++) {
                for (int j = 0; j < colsize; j++) {
                    arr[i][j] = copied[i][j];
                }
            }
        }

    }

    static int[][] arr = new int[300][300];
    static int[][] copied = new int[300][300];
    static Queue<point> q = new ArrayDeque<>();
    static boolean[][]  visited = null;
    static int check(){
        visited=new boolean[300][300];
        point firstOne = q.peek();
        dfs(firstOne.row,firstOne.col);
        Iterator<point> itr = q.iterator();
        while(itr.hasNext()){
            point temp=itr.next();
            if(!visited[temp.row][temp.col]) { //dfs로 방문안한게있다 == 쪼개졌다.
                return -1;
            }
        }
        return 1;
    }
    static void dfs(int row,int col){
        int[]x={0,0,-1,1};
        int[]y={1,-1,0,0};
        visited[row][col]=true;
        for(int i=0;i<4;i++){
            int dy=row+y[i];
            int dx=col+x[i];
            if(arr[dy][dx]!=0 && !visited[dy][dx]){
                dfs(dy,dx);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer token = new StringTokenizer(str);
        rowsize = Integer.parseInt(token.nextToken());
        colsize = Integer.parseInt(token.nextToken());
        int result=0;
        for (int i = 0; i < rowsize; i++) {
            str = br.readLine();
            token = new StringTokenizer(str);
            for (int j = 0; j < colsize; j++) {
                arr[i][j] = Integer.parseInt(token.nextToken());
                if (arr[i][j] > 0) {
                    q.add(new point(i, j));
                }
            }
        }
        int[]x={0,0,-1,1};
        int[]y={1,-1,0,0};
        int count=0;
        while (!q.isEmpty()) {
            int len = q.size();
            copyFunc(1);//복사본생성
            for (int i = 0; i < len; i++) {
                point temp=q.poll();
                int waterCount=0;
                for(int j=0;j<4;j++){
                    int dy=temp.row+y[j];
                    int dx=temp.col+x[j];
                    if(arr[dy][dx]==0){
                        waterCount++;
                    }
                }
                copied[temp.row][temp.col]-=waterCount;
                if(copied[temp.row][temp.col]<=0){
                    copied[temp.row][temp.col]=0;
                }
                else{
                    q.add(new point(temp.row,temp.col));
                }
            }
            copyFunc(2);
            count++;
//            for(int i=0;i<rowsize;i++){
//                for(int j=0;j<colsize;j++){
//                    System.out.print(arr[i][j]);
//                }
//                System.out.println();
//            }
//            System.out.println();
            if(q.isEmpty()) break;
            int checked=check();
            if(checked==-1){
                result=count;
                System.out.println(result);
                return;
            }
        }
        System.out.println(result);
    }
}