[Baekjoon] 2573번: 빙산 - Java

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

2573번: 빙산

문제 설명

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하면 된다. DFS와 BFS를 조합해야 할 거 같다는 생각은 들었는데 구현이 되지 않아 다른 풀이글을 참고했다. 핵심은 방문 기록을 매 반복마다 새로 사용하는 것이었다. 지금까지 풀어온 문제들은 한 번의 순회로 모두 해결되었었는데 이번 문제는 방문 기록을 매번 새로 사용해서 해결해야 했다.

풀이 방법 1. DFS+BFS

https://steady-coding.tistory.com/17

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

이 분의 풀이를 참고했다.

package baekjoon.dfs_bfs;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ2573 {

    static int N, M;
    static int[][] map;
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");

            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1]);

            map = new int[N][M];

            for (int i = 0; i < N; i++) {
                int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                        .toArray();
                for (int j = 0; j < M; j++) {
                    map[i][j] = line[j];
                }
            }

            int ans = 0, cnt = 0;
            while ((cnt = calcDividedBerg()) < 2) {
                if (cnt == 0) {
                    ans = 0;
                    break;
                }
                bfs();
                ans++;
            }

            System.out.println(ans);
        }
    }

    private static int calcDividedBerg() {
        boolean[][] isVisited = 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 && !isVisited[i][j]) {
                    dfs(i, j, isVisited);
                    cnt++;
                }
            }
        }

        return cnt;
    }

    private static void dfs(int x, int y, boolean[][] isVisited) {
        isVisited[x][y] = true;

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

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;

            if (map[nextX][nextY] > 0 && !isVisited[nextX][nextY])
                dfs(nextX, nextY, isVisited);
        }
    }

    private static void bfs() {
        Queue<Pos> queue = new LinkedList<>();

        boolean[][] isVisited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] > 0) {
                    queue.add(new Pos(i, j));
                    isVisited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            Pos pos = queue.remove();

            int seaCnt = 0;

            for (int i = 0; i < 4; i++) {
                int adjX = pos.getX() + dx[i];
                int adjY = pos.getY() + dy[i];

                if (adjX < 0 || adjY < 0 || adjX >= N || adjY >= M)
                    continue;

                if (!isVisited[adjX][adjY] && map[adjX][adjY] <= 0)
                    seaCnt++;
            }

            if (map[pos.getX()][pos.getY()] - seaCnt < 0)
                map[pos.getX()][pos.getY()] = 0;
            else
                map[pos.getX()][pos.getY()] -= seaCnt;
        }
    }

    static class Pos {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

풀이 방법 2. DFS

1번 방법으로 풀고 난 뒤 다른 사람들의 정답을 확인해보는데 내 제출보다 시간&메모리가 훨씬 적은 ilovekdh1208님의 코드를 발견했고 이렇게도 풀 수 있다는 걸 알게 됐다. https://www.acmicpc.net/user/ilovekdh1208

private static void dfs(int x, int y, boolean[][] isVisited) {
    isVisited[x][y] = true;

    // 빙산인 곳을 먼저 DFS로 모두 찾아낸다.
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
            continue;

        if (map[nextX][nextY] > 0 && !isVisited[nextX][nextY])
            dfs(nextX, nextY, isVisited);
    }

    // 빙산인 곳에서 근처가 바다인 곳을 체크하고 녹인다.
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
            continue;

        if (map[nextX][nextY] == 0 && !isVisited[nextX][nextY])
            map[x][y]--;
    }

    if (map[x][y] < 0)
        map[x][y] = 0;
}

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

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

public class BOJ2573 {

    static int N, M;
    static int[][] map;
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");

            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1]);
            map = new int[N][M];

            boolean[][] isVisited;

            for (int i = 0; i < N; i++) {
                int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                        .toArray();
                for (int j = 0; j < M; j++) {
                    map[i][j] = line[j];
                }
            }

            int ans = 0;
            Loop1: while (true) {
                isVisited = new boolean[N][M];
                boolean flag = false;
                boolean allMelt = true;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (map[i][j] > 0 && !isVisited[i][j]) {
                            if (flag)
                                break Loop1;
                            else
                                flag = true;
                            allMelt = false;
                            dfs(i, j, isVisited);
                        }
                    }
                }
                if (allMelt) {
                    System.out.println(0);
                    return;
                }
                ans++;
            }

            System.out.println(ans);
        }
    }

    private static void dfs(int x, int y, boolean[][] isVisited) {
        isVisited[x][y] = true;

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

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;

            if (map[nextX][nextY] > 0 && !isVisited[nextX][nextY])
                dfs(nextX, nextY, isVisited);
        }

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

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;

            if (map[nextX][nextY] == 0 && !isVisited[nextX][nextY])
                map[x][y]--;
        }

        if (map[x][y] < 0)
            map[x][y] = 0;
    }
}