[BOJ] 2573. 빙산

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

접근 방법

빙산의 맵을 받은 후 저장을 해가면서 융해→2덩어리로 확인을

반복하면 되는 문제이다.

주의할 점

Need Know

1. BFS

전체 코드 ( Java )

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static int[][] map;
    static int[][] copyMap;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visit;
    static int result = 0;
    public static void main(String[] args) throws IOException{
        set();
        solve();

        br.close();
        bw.flush();
        bw.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<M; k++){
                map[i][k] = Integer.parseInt(st.nextToken());
            }
        }
    }
    static void solve() throws IOException {
        while(true){
            if(!possible()){
                bw.write("0");
                return;
            }
            melting();
            if(!possible()){
                bw.write("0");
                return;
            }
            result++;
            if(check()){
                bw.write(result+"");
                return;
            }

        }
    }
    static boolean possible(){
        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                if(map[i][k] != 0) return true;
            }
        }
        return false;
    }
    static boolean check(){
        int count = 0;

        Queue<Point> queue = new LinkedList<>();
        visit = new boolean[N][M];
        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                if(!visit[i][k] && map[i][k] != 0){
                    queue.add(new Point(i,k));
                    count++;
                    while(!queue.isEmpty()){
                        Point now = queue.poll();

                        for(int z = 0; z < 4; z++){
                            int nx = now.x + dx[z];
                            int ny = now.y + dy[z];

                            if( nx<0 || ny<0 || nx>=N || ny>=M) continue;

                            if(!visit[nx][ny] && map[nx][ny] > 0){
                                queue.add(new Point(nx,ny));
                                visit[nx][ny] = true;
                            }
                        }
                    }
                }
            }
        }
        if(count >= 2){
            return true;
        }
        else {
            return false;
        }
    }
    static void melting(){
        copyMap = new int[N][M];
        for(int i=0; i<N; i++){
            copyMap[i] = map[i].clone();
        }

        for(int i=0; i<N; i++){
            for(int k=0; k<M; k++){
                if(copyMap[i][k] != 0){
                    int temper = 0;
                    for(int z=0; z<4; z++){
                        int nx = i + dx[z];
                        int ny = k + dy[z];

                        if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
                        if(copyMap[nx][ny] == 0) temper ++;
                    }
                    if(map[i][k] >= temper){
                        map[i][k] -= temper;
                    }else{
                        map[i][k] = 0;
                    }
                }
            }
        }
    }
    static class Point{
        int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}