백준 2573번 : 빙산 java

이 문제는 너비 우선 탐색을 여러 번 활용하여 문제에서 주어진 조건에 맞게 프로그램을 만드는 문제입니다.

저는 이 문제를 풀기 위해서 빙산이 이어져 있나를 확인하기 위해서 bfs를 먼저 한번 사용하였고 빙산이 1개로 이어져 있을 경우 빙산을 녹여야 하기 때문에 이때 bfs를 한번 더 사용하였습니다.

빙산이 2개 이상이 되었을 경우에는 그렇게 되기 까지의 시간을 출력하여 주었고 빙산이 0개가 되었을 경우에는 빙산이 다 녹을 때까지 분리되지 않았음을 의미하므로 0을 출력해줍니다.

---

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 j = 0; j<M; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        int year = icebergCount();
        System.out.println(year);
    }

    static int icebergCount(){
        int year;
        int loop = 0;

        //빙산의 갯수 확인
        while(true){
            visited = new boolean[N][M];
            int icebergCount = 0;

            for(int i = 0; i<N; i++){
                for(int j = 0; j<M; j++){
                    if(map[i][j] == 0)
                        continue;
                    if(visited[i][j])
                        continue;

                    icebergFind(i, j);
                    icebergCount++;
                }
            }

            // 빙산이 없거나 2개 이상이면 break
            if(icebergCount == 0) {
                year = 0;
                break;
            }
            else if(icebergCount != 1){
                year = loop;
                break;
            }

            icebergMelt();
            loop++;
        }

        return year;
    }

    //이어져 있는 빙산의 범위를 확인
    static void icebergFind(int row, int col){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(row, col, 0));
        visited[row][col] = true;

        while(!q.isEmpty()){
            Node a = q.poll();

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<0||dc<0||dr>=N||dc>=M)
                    continue;
                if(visited[dr][dc])
                    continue;
                if(map[dr][dc] == 0)
                    continue;

                visited[dr][dc] = true;
                q.offer(new Node(dr, dc));
            }
        }
    }

    //얼음 녹이기
    static void icebergMelt(){
        Queue<Node> q = new LinkedList<>();

        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(map[i][j] != 0){
                    int extent = meltExtent(i, j);

                    q.offer(new Node(i, j, extent));
                }
            }
        }

        while(!q.isEmpty()){
            Node a = q.poll();
            map[a.row][a.col] -= a.edge;

            if(map[a.row][a.col]<0)
                map[a.row][a.col] = 0;
        }
    }

    static int meltExtent(int row, int col){
        int extent = 0;

        for(int i = 0; i<4; i++){
            int dr = row + dR[i];
            int dc = col + dC[i];

            if(dr<0||dc<0||dr>=N||dc>=M)
                continue;

            if(map[dr][dc] == 0)
                extent++;
        }

        return extent;
    }
}
class Node{
    int row, col, edge;

    Node(int row, int col){
        this.row = row;
        this.col = col;
    }
    Node(int row, int col, int edge){
        this.row = row;
        this.col = col;
        this.edge = edge;
    }
}

문제에서 요구하는 조건들을 차례대로 구현하면 쉽게 해결할 수 있는 문제였습니다.