[BOJ] 백준 2573 - 빙산 풀이

1. 문제

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

2573번: 빙산

 

2. 풀이

백준 골드4에 해당하는 DFS 문제이다.
우선 입력으로 주어지는 배열의 row와 column을 통해 정수형 2차원 배열을 구성하고 다음 줄부터 주어지는 배열의 값을 2차원 배열에 값을 저장한다.

그 후 while 무한 반복을 돌면서 다음과 같은 로직을 순서대로 수행한다.
1. 1년 추가

2. 얼음 구역의 개수 체크 ( 이는 처음으로 주어지는 배열의 값이 이미 다 녹아있거나 이미 두 덩어리로 분리되어 있는 경우가 있으므로. )

3. 2번의 체크로 이미 얼음이 다 녹아있거나 두 덩어리로 분리되어 있다면 -> 반복문 탈출

4. 3번에서 반복문을 탈출하지 않았다면 else 실행

5. 얼음이 녹을 수 있는 부분 체크
얼음이 녹을 수 있는 부분을 체크하고 그 부분에서 동서남북으로 0이 몇 개가 있는지 체크한다.

처음 문제를 풀 때 0이 아닌 부분을 하나씩 체크하여 녹는 것을 처리했더니 연속해서 녹아버리는 문제가 발생했었다. 예를 들어, 문제에서 주어지는 배열 값 중 2행 2열, 2행 3열 값을 보면 2와 4이다. 1년이 지난 후 이 두 값은 0과 2가 된다. 만약 하나씩 체크하여 녹는 것을 먼저 처리해버리면 1년이 지난 후 2와 4의 값은 0과 1이 된다. 이유는 2를 먼저 처리했을 경우 0이 되버리기 때문에 4를 체크할 때 동서남북에 0이 3개가 되어 버리기 때문이다.

따라서 녹을 수 있는 점을 먼저 리스트에 저장해서 나중에 처리해야 한다.

6. 얼음이 실제 녹는 로직
리스트에 넣은 점을 하나씩 탐색하면서 얼음의 양을 체크하여 계산한다. 이 때, 현재 얼음의 양 - 체크한 0의 개수가 0보다 작다면 0을 넣고 아니라면 뺀 값을 넣는다.
그 후 리스트를 clear를 해준다.

7. 얼음 구역 다시 체크
얼음을 녹는 로직을 수행했으니 현재 얼음 구역이 몇 개 있는지 체크한다.

8. 7에서 체크한 얼음 구역이 2개 이상이라면 반복문을 빠져나간다.

마지막으로 계산한 년수를 출력해주면 정답!!!

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;

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

    static class Point {
        int x;
        int y;
        int waterCnt;

        public Point(int x, int y, int waterCnt) {
            this.x = x;
            this.y = y;
            this.waterCnt = waterCnt;
        }
    }

    static ArrayList<Point> points = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[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());
            }
        }

        int years = 0;
        while (true) {
            years++;

            // 얼음 구역의 개수 체크
            int firstCnt = 0;
            visited = new boolean[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] != 0 && !visited[i][j]) {
                        IceCnt(i, j);
                        firstCnt += 1;
                    }
                }
            }

            if (firstCnt == 0 || firstCnt >= 2) {
                years = 0;
                break;
            } else {
                // 얼음이 녹을 수 있는 점을 체크하는 로직
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (map[i][j] != 0) {
                            IceMalt(i, j);
                        }
                    }
                }

                // 얼음이 실제 녹는 로직
                for (int i = 0; i < points.size(); i++) {
                    if (map[points.get(i).x][points.get(i).y] - points.get(i).waterCnt < 0) {
                        map[points.get(i).x][points.get(i).y] = 0;
                    } else {
                        map[points.get(i).x][points.get(i).y] -= points.get(i).waterCnt;
                    }
                }
                points.clear();

                // 얼음 구역의 개수 체크
                visited = new boolean[N][M];
                int cnt = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (map[i][j] != 0 && !visited[i][j]) {
                            IceCnt(i, j);
                            cnt += 1;
                        }
                    }
                }

                // 열음 구역의 개수가 2가 넘거나 전부 녹을 때까지 두 덩어리 이상으로 분리되지 않는다면
                if (cnt >= 2) {
                    break;
                }
            }
        }

        bw.write(Integer.toString(years));
        bw.flush();
        bw.close();
        br.close();
    }

    static void IceCnt(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (xf >= 0 && xf < N && yf >= 0 && yf < M && !visited[xf][yf] && map[xf][yf] != 0) {
                IceCnt(xf, yf);
            }
        }
    }

    static void IceMalt(int x, int y) {
        int waterCntMethod = 0;
        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (map[xf][yf] == 0) {
                waterCntMethod += 1;
            }
        }

        if (waterCntMethod > 0) {
            points.add(new Point(x, y, waterCntMethod));
        }
    }
}