[Java] 백준 2573.빙산

문제

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

2573번: 빙산

알아야 할 개념

• 독해력
• DFS 구현

풀이

나의 부족한 문제 이해력으로 문제의 예외 캐이스를 미쳐 생각 못해 머리를 싸메다 백준 질문 게시판에서 힌트를 얻었다.

dfs구현은 어렵지 않았지만 예외 케이스가 존재하였다.

바로 빙산이 한번에 녹아 버리는 경우이다.

문제를 다시 보자

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

 

빙산이 녹기 시작하고,k 시간이 지난 후  한번에 녹아버려 배열의 값이 모두 0 이될 경우 답은 0 을 출력해야 한다.

두 덩어리 이상으로 분리가 된게 아니기 때문이다.  따라서 0 을 출력한다. 문제 조건에 명확히 명시 되지 않아 예외를 놓쳤지만  , 이정도는 도출 가능할 거라 생각하면서 문제를 만드신 듯 하다

 

풀이 알고리즘은 다음과 같다.

1. 처음부터 바다 ( 0 값) 가 존재하지 않으면 0 을 출력한다
2. 반복문을 돌면서 다음을 수행한다.
   1. 2차원 배열을 모두 탐색하여 전부 녹았을 경우 0을 출력한다.
   2. 시간 1 증가
   3. 녹을 위치를 큐에 담아 얼음을 녹인다.
   4. 2개 이상 분리됬을 경우 반복문을 탈출한다.

 

코드

import java.io.*;
import java.util.*;
public class Main {

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

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.solution();
    }
    public void solution() throws IOException {
        FastReader fr = new FastReader();
        int N = fr.nextInt();
        int M = fr.nextInt();
        int arr[][] = new int[N][M];
        for(int i =0 ;i < arr.length;i ++){
            for(int j = 0 ;j < arr[0].length;j ++){
                arr[i][j] = fr.nextInt();
            }
        }
        boolean flag = true;
        int ans = 0;
        Queue<int[]> Q = new LinkedList<>();
        if(!isnoIce(arr)){
            while(flag){
                if(findIceMountain(Q, arr) == false){//전부 녹았을 경우
                    ans = 0;
                    break;
                }
                ans++;//시간 1 증가
                while(!Q.isEmpty()){//녹을 위치를 큐에 담아 얼음을 녹인다.
                    int c[] = Q.poll();
                    arr[c[0]][c[1]] = arr[c[0]][c[1]] > c[2] ? arr[c[0]][c[1]]-c[2] : 0;
                }
                if(moreThanTwo(arr, new boolean[N][M]))break;//2개 이상 분리됬을 경우 반복문을 탈출한다.
            }
        }else ans = 0;//처음부터 바다 ( 0 값) 가 존재하지 않으면 0 을 출력한다

        System.out.println(ans);
    }
    public boolean isnoIce(int[][]a){
        for(int i =0 ;i < a.length; i++){
            for(int j= 0;j < a[0].length;j ++){
                if(a[i][j] == 0)return false;
            }
        }
        return true;
    }
    public boolean findIceMountain(Queue<int[]> Q, int[][]m){
        int zeroVal =0;
        for(int i =0;i < m.length; i++){
            for(int j= 0 ;j < m[0].length;j ++){
                if(m[i][j] >0 ){
                    zeroVal = 0;
                    for(int k = 0 ; k < 4; k++){//count zeroVal
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if(nx < 0 || ny < 0 || nx > m.length -1 || ny > m[0].length-1 || m[nx][ny] > 0)continue;
                        zeroVal++;
                    }
                    Q.offer(new int[]{i,j,zeroVal});
                }
            }
        }
        return !Q.isEmpty();// return true if Q is not Empty.
    }
    public boolean moreThanTwo(int[][]m, boolean[][] v){
        int cnt=0;
        for(int i = 0 ;i < m.length;i ++){
            for(int j= 0 ;j < m[0].length;j ++){
                if(m[i][j] > 0 && !v[i][j]){
                    if(cnt > 0)return true;
                    v[i][j] = true;
                    cnt++;
                    dfs(m,i,j,v);
                }
            }
        }
        return false;
    }
    public void dfs( int[][]m, int x, int y, boolean[][] v){
        for(int k = 0 ;k < 4 ;k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx > m.length -1 || ny > m[0].length-1 || m[nx][ny] ==0 || v[nx][ny])continue;
            v[nx][ny] = true;
            dfs(m, nx, ny,v);
        }
    }
    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}