[백준/JAVA] 2573번: 빙산

🔺 문제

2573번: 빙산

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int N, M;
 
    static int[][] map, melt;
    static boolean[][] visited;
 
    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];
        melt = new int[N][M];
        visited = new boolean[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());
            }
        }
 
        solve();
    }
 
    private static void solve() {
        int year = 0;
        
        // 1. 빙산 덩어리 세기 (DFS)
        while (true) {
            int parts = 0;    // 빙산 덩어리 수
            
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] != 0 && !visited[i][j]) {
                        dfs(i, j);
                        parts++;
                    }
                }
            }
 
            if (parts == 0) {
                System.out.println(0);
                break;
            }
            else if(parts >= 2) {
                System.out.println(year);
                break;
            }
            
            melt();    // 2. 녹이기
            year++;
        }        
    }
 
    static void dfs(int x, int y) {
        visited[x][y] = true;
        
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
            
            // 1년 후 녹는 빙산 양 계산
            if(map[nx][ny] == 0)
                melt[x][y]++;
                
            // dfs 재귀
            if(!visited[nx][ny] && map[nx][ny] != 0)
                dfs(nx, ny);
        }
    }
    
    static void melt() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                map[i][j] -= melt[i][j];            // 1) 빙산 녹이기
                
                if(map[i][j] < 0)   map[i][j] = 0;  // 2) 음수가 되면, 0으로 바꾸기
                
                visited[i][j] = false;              // 3) visited 초기화
                melt[i][j] = 0;                     // 4) melt 초기화
            }
        }
    }
}
 

 

 

🧩 해결 아이디어

1. 빙산 덩어리 수 세기 (DFS)

 - 덩어리 수가 0개면 0 출력 / 2개 이상이면, 연도 출력

 - 둘 다 아니면, 빙산 녹이고, 연도 + 1

 

 

 

2. 근처 0의 갯수만큼 녹이기

  2-1. 2차원 배열 melt 활용

    1) 녹이기 = melt 배열의 값만큼 빼기

    2) 녹이고 난 후의 값이 0보다 작다면, 0으로 조절

    3) 녹이고 난 후, 다음 빙산 갯수 확인하기 위해 visited 배열, melt 배열 값 초기화

 2-2. 근처에 0이 아닌 수가 있다면, DFS 재귀

 

 

---

🔺 다른 풀이들

- 빙산 덩어리 수 구하고, 녹이는 과정에서 BFS를 활용하셨다.

[백준] 2573번 - 빙산 (java)

 

[BOJ] 백준 2573번 : 빙산 (JAVA)

 

 

- DFS + BFS 섞어서 푸셨따.

[BOJ] 백준 2573번 : 빙산 (JAVA)

---

💬 느낀 점

손으로 로직을 잘 작성해두고 구현해야겠다....

중간에 생각하다가 꼬여서 헥... 싶었음...

 

 

1회독	2회독	3회독	4회독	5회독
V	240307

---

(참고)

백준 2573번. 빙산 (Java)