[BeakJoon] 2573 빙산 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

해당 문제는 1년 단위로 각각의 구역은 인접한 바다의 칸 만큼의 높이가 감소하게 하게 하며 빙산이 2조각 이상으로 쪼개질 경우 그때까지 몇년이 걸렸는지 체크하는 문제입니다.

최근 우테코 프리코스를 통해 배운 내용을 바탕으로 기능별로 메서드를 분리하여 문제를 풀어보며 main메서드를 제외한 5개의 메서드를 생성하여 풀이하였습니다.

각각의 메서드는 다음과 같은 역할을 합니다.
meltForYear(): melt 메서드를 호출하여 한 해가 지남에 따른 빙산의 높이(matrix)를 업데이트 해준다.
melt(): 해당 칸에 인접한 바닷물 칸을 체크하며 변하는 빙산의 높이를 return해준다.
checkSeparate(): 빙산이 두 덩이 이상으로 나뉘었는지 체크를 하는 메서드입니다.
dfs(): checkSeparate()에서 호출되어 바다가 아닌 인접한 빙산 칸들을 순회하며 체크한다.
checkAllMelt(): 빙산이 모두 녹았는지 체크해주는 역할을 해줍니다.

처음 문제를 풀고나서 시간초과가 나와서 많은 시간을 소모하였습니다.
첫 풀이의 시간초과 이유는 checkAllMelt()메서드의 부재로 빙산이 모두 녹을 떄까지 두 덩이 이상의 빙산으로 분리되지 않기 때문에 메인 메서드가 무한 루프에 빠지게 되어 시간초과라는 결과가 나왔습니다.
💡 문제를 풀고 시간초과가 나온다면 저처럼 문제를 다시 읽고 놓친 조건이 없는지 체크하시기 바랍니다.

👨🏻‍💻 작성한 코드

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

public class Main {
    static int N;
    static int M;
    static int[][] matrix;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    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());
        matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0;
        while (!checkSeparate()) {
            meltForYear();
            result++;
            if (checkAllMelt()) {
                result = 0;
                break;
            }
        }
        System.out.println(result);
    }

    // 1년 단위로 높이 축소하는 메서드
    private static void meltForYear() {
        int[][] tempMatrix = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] > 0)
                    tempMatrix[i][j] = melt(i, j);
            }
        }
        matrix = tempMatrix;
    }

    // 각각의 칸을 녹이는 메서드
    private static int melt(int y, int x) {
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N || matrix[ny][nx] == 0) {
                count++;
            }
        }
        if (matrix[y][x] >= count) {
            return matrix[y][x] - count;
        }
        return 0;
    }

    // 두 덩이 이상으로 나뉘었는지 체크하는 메서드
    private static boolean checkSeparate() {
        boolean[][] checked = new boolean[N][M];
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] > 0 && !checked[i][j]) {
                    dfs(i, j, checked);
                    count++;
                }
                if (count >= 2) return true;
            }
        }
        return false;
    }

    // dfs 탐색 메서드
    private static void dfs(int y, int x, boolean[][] checked) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N || matrix[ny][nx] == 0 || checked[ny][nx]) {
                continue;
            }
            checked[ny][nx] = true;
            dfs(ny, nx, checked);
        }
    }

    // 빙산이 모두 녹았는지 체크
    private static boolean checkAllMelt() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }
}