[백준] 2573번 : 빙산

빙산

---

풀이 방법

머리로는 어떻게 구현할지 쉽게 생각한 문제였다.

먼저

• 주어진 빙산이 두 덩어리로 분리되는지 확인
• 한 덩어리라면 녹인다(1년 지남).
  • 만약 두 덩어리로 나누어지면 녹인 횟수를 출력.
  • 끝까지 나누어지지 않는 경우라면 0을 출력

중요한 알고리즘은 DFS를 통해 이웃한 빙산을 탐색을해서 몇 개의 덩어리로 나누어지는지 확인하고,

탐색 중 각 빙산 주위의 바다의 수를 체크해서 녹일 때 빼주면 되는 문제였다.

다른 풀이

녹이는 함수 Melt() 구현시에 BFS로 구현한 풀이가 있었다. 근데 DFS에서 구현한 각 빙산 주위의 바다 존재를 체크하는 함수를 또 사용하는 방식이라 굳이 그렇게 구현하지 않았다.

자세한건 주석을 단 소스코드를 확인하자

느낀 점

이번 문제는 골드 문제 중에서 가장 고민을 적게하고 접근한 문제였다. 하지만, 아직 DFS를 정확하지 이해하지 못한건지 덩어리를 구하는 부분에서 조금 헤맸다.

재귀함수 부분을 좀 더 확실히 이해하는게 중요하다는 것을 느꼈다. 재귀는 많이 부딪혀보자!

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] ground;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int n;
    static int m;
    static boolean[][] visited;
    static int[][] melt;
    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());
        ground = new int[n][m];
        melt = new int[n][m];
        //빙산 구성
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<m;j++){
                ground[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int count = 0;
        while(true){
            //두 덩어리 이상으로 분리되는지 체크
            int num = countIceberg();
            if(num == 0 ){ //끝까지 나누어지지 않으면
                count = 0;
                break;
            }
            else if(num >= 2) { //2덩어리 이상으로 나누어지면
                break;
            }
            //녹이기
            Melt();
            count++;
        }
        System.out.println(count);
    }
    private static int countIceberg() {
        visited = new boolean[n][m];
        int count = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j] && ground[i][j] != 0){
                    dfs(i,j); //총 몇 개의 빙하로 나누어 졌는지 알 수 있다.
                    count++;
                }
            }
        }

        return count;
    }
    private static void dfs(int x, int y){
        visited[x][y] = true;

        for(int i=0;i<4;i++){
            int mx = x + dx[i];
            int my = y + dy[i];

            if(mx>=0 && my>=0 && mx<n && my<m){
                if(ground[mx][my] == 0) //주변이 바다라면 melt배열에 개수 저장
                    melt[x][y]++;

                if(ground[mx][my] != 0 && !visited[mx][my]) //값이 있고, 방문하지 않았으면 계속 탐색
                    dfs(mx, my);
            }
        }
    }
    private static void Melt() {
        for(int i=0;i<n;i++) {
            for (int j = 0; j < m; j++) {
                ground[i][j] -= melt[i][j]; //각 빙산마다 주변의 바다의 수를 뺌
                if (ground[i][j] < 0) //음수 처리
                    ground[i][j] = 0;
                melt[i][j] = 0; //초기화
            }
        }
    }
}