[백준] 2573번: 빙산

2573번: 빙산

• 빙산은 1년마다 녹는다.
• 빙산의 높이는
  • 해당 칸의 동서남북 네 방향으로 붙어있는 0인 칸의 개수만큼 줄어든다.
  • 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.
• 하나의 빙산 :
  • 동서남북으로 연결된 0이아닌 칸들은 하나의 빙산을 이룬다.
• 구해야 할 것 :
  • 빙산이 [ 두 덩어리 이상으로 분리되는 최초의 시간 ] 을 구하는 프로그램
  • 전부 다 녹을 때 까지, 두 덩어리 이상으로 분리되지 않으면, 0을 출력할 것
• 주어진 것 : 행(N), 열(M)
  • N과 M은 3이상 300이하

문제 풀이

(00:45)

• Tree의 개수를 구하여 반환하는 함수 작성
  • 초기화된 visit을 갖고 한다.
  • 전체 탐색하며 → 0이 아님 && visit하지 않은 칸 을 마주하면 , DFS를 한다 → traverse하는 칸은 visit으로 체크한다.
  • cnt가 2가 되는 순간 stop하고 2를 반환한다.
  • 처음 시작할 때에도 이것을 처리한다.
• 1년 마다 빙산은 녹는다.

  • board를 두개 두도록 한다.

  • next는 pre를 기반으로 작성한다. ( next를 next를 기반으로 하면 안 된다. 왜냐하면,

    

    여기서, 2부터 녹는 것과 관련한 처리를 하면 → next에서는 0이 되어버린다.

    4가 녹는 것에 대해 처리할 때, next를 기반으로 하면, 4의 서쪽도 0이기 때문에 4에서 3을 빼버리게 되기 때문이다.

  • 근데 이렇게 되면, 매 번 최대 9만개를 복사해야함.

  • 아 그래도 괜찮다. 왜냐하면 빙하의 높이는 최대 10이기 때문에

  • 9만정도씩 복사하는 걸 100번 정도 하는것 까지는 괜찮다.

    빙산이 녹은 후 해야할 일

    1. 그래프의 개수를 구하는 함수를 작동

       → 0인 경우 → stop && 0을 출력.

       → 2인 경우 → 년수를 출력한다.

package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static int n,m;
    public static int[][] dirs=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public static int[][] board;
    public static boolean[][] visit;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        visit = new boolean[n][m];
        for(int r=0;r<n;r++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<m;c++){
                board[r][c] = Integer.parseInt(st.nextToken());
            }
        }
    }
    public static int solve() {
        int cnt=0; // 빙산 개수
        int y=0; // 년도
        int[][] next = new int[n][m];
        // next를 pre에서 복사한다.
        copy(next,board);
        while(true) {
            cnt = evalCnt(board);
            if (cnt == 0) return 0;
            else if (cnt>=2) return y;
            // 녹는다 -> 녹은 결과가 next에.
            melt(board,next);
            // board를 next로 업데이트
            copy(board,next);
            y++;
        }
    }
    public static void melt(int[][] cb,int[][] next){
        int nr=0,nc=0;
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                // 빙산인 [r][c]에 대해서만
                if(cb[r][c]<=0)continue;
                for(int dir=0;dir<dirs.length;dir++){
                    nr = r+dirs[dir][0];
                    nc = c+dirs[dir][1];
                    //범위 넘으면 패스
                    if(nr<0||nc<0||nr>=n||nc>=m)continue;
                    // 그냥 음수가 될 수도 있게 해주었다.
                    if(cb[nr][nc]<=0)next[r][c]--;
                }
            }
        }
    }
    public static void copy(int[][] next,int[][] cb){
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                next[r][c]=cb[r][c];
            }
        }
    }
    //cb: current board
    // evaluate the number of trees
    // 0 보다 큰 칸이 아무것도 없는 경우 == 빙산이 모두녹은 경우 -> return 0
    public static int evalCnt(int[][] cb){
        int cnt=0;
        // visit array init
        for(int r=0;r<n;r++)Arrays.fill(visit[r],false);

        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                if(visit[r][c]==false&&cb[r][c]>0){
                    cnt++;
                    visit[r][c]=true;
                    dfs(r,c,cb);
                }
                if(cnt>=2)break;
            }
        }
        return cnt;
    }

    public static void dfs(int r, int c,int[][] cb){
        int nc=0,nr=0;
        for(int dir=0;dir<dirs.length;dir++){
            nr = r + dirs[dir][0];
            nc = c + dirs[dir][1];
            if(nr<=0||nc<=0||nr>=n||nc>=m) continue;
            //빙산이 아니면 패스
            if(cb[nr][nc]<=0)continue;
            //이미 방문했으면 패스
            if(visit[nr][nc])continue;
            // 방문 처리해준다.
            visit[nr][nc]=true;
            dfs(nr,nc,cb);
        }
    }
    public static void main(String[] args) throws IOException {
        setting();
        int y = solve();
        System.out.println(y);
    }
}

실수했던 부분

내 무덤을 내가 판 부분
음수가 될 수도 있게 해 놓았다.
따라서, <=0 을 검증해야하는 부분들이 있었는데, 이걸 ==0 으로 검증해서 버그를 계속 찾지 못한 부분들이 있었다.