[白俊]2573号:氷山

問題を解く

nextはpreに基づいて作成されます.(nextはnextに基づいてはならない.

ここで、2から溶融に関する処理を開始すると、→nextは0となる.
処理4の溶融時にnextをベースにすれば4の西も0であるので4から3を減算する.

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

ミス