[BOJ] 백준 2573. 빙산

문제

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

2573번: 빙산

---

풀이

 BFS 문제입니다. 

 

 구역의 개수가 2이상이거나, 얼음이 존재하지 않을 때까지 반복문을 통해 얼음을 녹여야 합니다.

 

 addIce()
 meltIce()
 checkBlock()

의 세 가지 메서드 순서로 분리해서 문제를 해결했습니다. 

 

 addIce()는 map[][] 배열의 얼음을 queue 자료 구조에 집어 넣는 메서드입니다. 그리고 동시에 다음 연도에 얼마나 줄어들지를 카운트해서 decrease[][] 배열에 저장해 줍니다.

 

 meltIce()는 map[][] 배열의 얼음을 decrease[][] 배열을 통해 녹여줍니다.

 

 checkBlock()은 map[][]에 존재하는 얼음 덩어리의 개수를 카운트해줍니다. 

 

위 순서를 반복하면서 종료 조건을 체크하고, 조건이 만족되면 while 문을 종료합니다.

 

 

 

---

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class B2573_빙산 {

    static int N,M;
    static int[][] map;
    static int[][] decrease;
    static boolean[][] visited;
    static int year;
    static int block;
    static boolean isIce;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];

        for(int r=0;r<N;r++){
            for(int c=0;c<M;c++){
                map[r][c] = sc.nextInt();
            }
        }
        isIce = false;
        year = 0;
        melt();
        if(!isIce) System.out.println(0);
        else System.out.println(year);
    }
    static void melt(){
        while(true) {
            addIce();
            meltIce();
            checkBlock();

            year++;
            if (block >= 2) break;
            if(!isIce) break;
        }
    }
    static void addIce(){
        Queue<int[]> ice = new LinkedList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] != 0) ice.add(new int[]{r, c});
            }
        }
        decrease = new int[N][M];
        while (!ice.isEmpty()) {
            int[] info = ice.poll();
            int r = info[0];
            int c = info[1];
            for (int i = 0; i < 4; i++) {
                int idr = r + dr[i];
                int idc = c + dc[i];
                if (map[idr][idc] == 0) decrease[r][c]++;
            }

        }
    }
    static void meltIce(){
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if(map[r][c] - decrease[r][c] <0) map[r][c] =0;
                else map[r][c] = map[r][c] - decrease[r][c];
            }
        }
    }
    static void checkBlock(){
        visited = new boolean[N][M];
        block = 0;
        isIce = false;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] != 0 && !visited[r][c]) {
                    bfs(r, c);
                    visited[r][c] = true;
                    block++;
                    isIce = true;
                }
            }
        }
    }
    static void bfs(int row, int col){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{row, col});
        visited[row][col] = true;
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int r = info[0];
            int c = info[1];
            visited[r][c] = true;
            for(int i=0;i<4;i++){
                int idr = r+dr[i];
                int idc = c+dc[i];
                if(visited[idr][idc]) continue;
                if(map[idr][idc]!=0){
                    queue.add(new int[]{idr,idc});
                    visited[idr][idc] = true;
                }
            }
        }
    }
}