2573-빙산

2573번: 빙산

 

빙산이 녹아 빙산 덩어가 2개 이상이 되는데 까지 몇 년이 걸리는지 구하는 문제이다.

필드의 row col 입력받고, 필드의 빙산 값들을 받아준다. (0이면 물? 1이상이면 빙산)

빙산의 동서남북중 하나라도 물에 닿고있다면 닿고있는 물의 수만큼 마이너스 해준다.

 

(0년차 - 입력값) 빙산들이 다 이어져있으니 1덩이

0 0 0 0 0 0 0 
0 2 4 5 3 0 0 
0 3 0 2 5 2 0 
0 7 6 2 4 0 0 
0 0 0 0 0 0 0

 

(1년차) 빙산들이 다 이어져있으니 1덩이

0 0 0 0 0 0 0 
0 0 2 4 1 0 0 
0 1 0 1 5 0 0 
0 5 4 1 2 0 0 
0 0 0 0 0 0 0 

 

(2년차)

0 0 0 0 0 0 0 
0 0 0 3 0 0 0 
0 0 0 0 4 0 0 
0 3 2 0 0 0 0 
0 0 0 0 0 0 0 

2년차가 되면 빙산이 3덩이가 되었다.

 

while문으로 빙산의 수 num이 1보다 커지면 years-1를 출력한다

 

왜 years-1을 출력하나?

for문을 돌며 너비 탐색에서 빙산의 수를 구하는데 

 

원래는 0년차 > 탐색후 빙산 수 구하기 > 녹이기 순으로 돌아야하는데 

내가 쓴 방법 ) 0년차 > 탐색과 동시에 빙산 녹이기 > 구하기

 

이 방법으로 해서 1년 뒤에 이전년도에 빙산 수가 구해진다

대신 for문 한번을 덜쓸수있지만 너무 보기도 불편하다

 

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

public class B2573 {
    static int N,M;
    static int[][] Board;
    static boolean[][] visited;
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};

    static class Node{
        int row,col;
        Node(int r, int c){
            row=r;
            col=c;
        }
    }

    public static void day() {
        int num =0;
        int years =0;


        while(num<2){
            num =0;
            boolean melt = false;
            visited = new boolean[N][M];
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(Board[i][j]!=0 && !visited[i][j]){
                        bfs(new Node(i,j));
                        num ++;
                        melt = true;
                    }
                }
            }
            if(!melt){
                years=1;
                break;
            }
            years++;
        }

        System.out.println(years-1);
    }

    private static void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        visited[node.row][node.col] = true;
        queue.add(node);

        while(!queue.isEmpty()){
            Node temp = queue.remove();

            int zero =0;
            for(int i=0; i<4; i++){
                int nr = temp.row + D[i][0];
                int nc = temp.col + D[i][1];

                if(visited[nr][nc]) continue;
                if(Board[nr][nc]==0) {
                    zero +=1;
                    continue;
                }
                visited[nr][nc] = true;
                queue.add(new Node(nr,nc));
            }
            if(Board[temp.row][temp.col]<zero) {
                Board[temp.row][temp.col]=0;
            }else{
                Board[temp.row][temp.col] -= zero;
            }
        }
    }


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

        Board = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                Board[i][j] = sc.nextInt();
            }
        }
        day();
    }
}

 

그래도 성공