[백준 2573] 빙산 / 자바 / dfs

#문제         

레벨:  G4
알고리즘:  dfs
풀이시간: 1시간
힌트 참조 유무:

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

 

---

 

#문제 풀이        

이 문제는 두가지를 구현하면 되는 문제이다.

1. 빙산의 개수 카운팅 함수
2. 빙산을 녹이는 함수

하지만 난 보다시피 dfs가 간접적으로 빙하를 카운팅 하는데 도움을 주면서 빙하를 녹였다. 원래 내생각에는 한번 배열을 순회하는 김에 다 처리하자. 그게 성능상 이점을 가져갈 것 같다였다. 그러나 두가지 일을 동시에 하는 코드를 짜니 코드를 짜기 복잡했다.

그래서 위에 쓴 과정처럼 논리의 흐름대로 코드를 짰다.

---

#풀이 코드      

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};
    static int row, col;
    static boolean[][] visited;
    static int[][] arr, meltArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());
        arr = new int[col][row];
        
        for (int i = 0; i < col; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < row; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = 0;
        while (true) {
            int icebergCount = countIcebergs();
            if (icebergCount >= 2) {
                System.out.println(ans);
                return;
            }
            if (icebergCount == 0) {
                System.out.println(0);
                return;
            }
            meltIceberg();
            ans++;
        }
    }

    static int countIcebergs() {
        visited = new boolean[col][row];
        int count = 0;
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                if (!visited[i][j] && arr[i][j] > 0) {
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    static void dfs(int y, int x) {
        visited[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx >= 0 && nx < row && ny >= 0 && ny < col && !visited[ny][nx] && arr[ny][nx] > 0) {
                dfs(ny, nx);
            }
        }
    }

    static void meltIceberg() {
        meltArr = new int[col][row];
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                if (arr[i][j] > 0) {
                    int zeroCount = countAdjacentZeros(i, j);
                    meltArr[i][j] = Math.max(0, arr[i][j] - zeroCount);
                }
            }
        }
        arr = meltArr;
    }

    static int countAdjacentZeros(int y, int x) {
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx >= 0 && nx < row && ny >= 0 && ny < col && arr[ny][nx] == 0) {
                count++;
            }
        }
        return count;
    }
}

---

#비슷한 유형     

https://jsw5913.tistory.com/180

[백준 2638] 자바 / 치즈 / bfs