[BOJ-2573] 빙산(JAVA)

백준 2573 빙산

 

2573번: 빙산

 

문제 설명

 

 - 지구 온난화로 북극의 빙산이 녹고 있다.

 

 - 빙산은 2차원 배열에 표시된다.

   바다는 0으로 빙산의 높이는 양의 정수로 표시된다.

 

 - 매해 바다와 인접한 빙산의 높이는 줄어진다.

   (빙산의 동서남북 방향에 붙어 있는 바다의 개수 만큼 매해 줄어든다.)

 

 - 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하라.

 

 - 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는다면 0을 출력하라.

 

---

 

입력 값

 

 - 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N, M이 한 개의 빈칸을 두고 주어진다.

 

 - N과 M은 3 이상 300 이하이다.

 

 - 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈칸을 두고 주어진다.

 

 - 각 칸에 들어가는 값은 0 이상 10 이하이다.

 

 - 배열에서 빙산이 차지하는 칸의 개수는 10,000개 이하이다.

 

 - 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 몇년이 되어야 빙산이 쪼개지는지 측정하는 문제이다.

 

 - 즉, 0년 부터 시작하여 빙산이 쪼개졌는가를 판단해야 한다.

 

 - 빙산을 쪼개는 방법은 첫 노드부터 마지막 노드까지 돌면서 바다인 노드와 인접한 빙산 노드의 값을 줄이면 된다.

   여기서 주의할 점은 바다에 의해서 빙산이 바다가 된 경우는 그해의 바다로 생각하면 안된다는 것이다.

   예를 들어 0 1 / 1 1 이 주어졌을 때 (0,0)에 의해서 (0,1) / (1,0)은 바다가 되지만 그 바다의 효력은 다음 해에 발휘된다.

 

 - 빙산이 쪼개졌는지는 BFS / DFS를 이용하여 판단할 수 있다.

 

 - 즉, 정리하자면

   1. 빙산을 쪼갠다.

   2. 빙산이 쪼개졌는지 확인한다.

   3. 쪼개졌다면, 몇년인지 리턴, 아니면 1번으로 돌아간다.

 

---

 

 

소스 코드

 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/2573
// 빙산
public class Main {

    public static int boards[][] = new int[301][301];

    public static int N, M;

    public static int dy[] = new int[]{1,-1,0,0};
    public static int dx[] = new int[]{0,0,1,-1};

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());

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

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

        int result=0;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<M;j++){
                boards[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        while(true){
            if(isSeperated()){
                break;
            }
            if(seperate()){
                result=0;
                break;
            }
            result++;
        }

        System.out.println(result);

    }

    public static boolean seperate(){

        int result[][] = new int[301][301];

        boolean isFinish=true;

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(boards[i][j]>0){
                    continue;
                }

                for(int d=0;d<4;d++){
                    int ny = i+dy[d];
                    int nx = j+dx[d];

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

                    result[ny][nx]--;

                }

            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                boards[i][j]+=result[i][j];
                if(boards[i][j]>=0){
                    isFinish=false;
                }
            }
        }
        return isFinish;
    }

    public static boolean isSeperated(){
        boolean check[][] = new boolean[301][301];

        int cnt=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(check[i][j] || boards[i][j]<=0){
                    continue;
                }

                check[i][j]=true;
                cnt++;

                Queue<Node> q = new LinkedList<>();
                q.add(new Node(i,j));

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

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

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

                        if(check[ny][nx] || boards[ny][nx]<=0){
                            continue;
                        }

                        check[ny][nx]=true;
                        q.add(new Node(ny,nx));

                    }

                }

            }
        }

        return cnt >= 2;

    }

    public static class Node{
        int y;
        int x;

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

}