[백준] 2573번 - 빙산 [Java]

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

 

[백준] 2573번 - 빙산 [Java]

[백준] 2573번 - 빙산 [Java]

[백준] 2573번 - 빙산 [Java]

[백준] 2573번 - 빙산 [Java]

---

1.  아이디어

 

빙산을 녹이는 로직과 빙산의 개수를 구하는 로직을 구분해서 해결했다. 빙산의 개수는 BFS, DFS 알고리즘으로 간단하게 구할 수 있다.

---

2. 문제풀이

 

빙산을 녹일 때 방금 녹여서 바닷물이 된 부분이 다시 옆 빙산을 녹이는 상황이 발생하게 돼서 각 빙산 주변의 바닷물을 따로 센 후 한번에 빼주는 것만 주의해서 구현하면 된다.

---

3. 코드

 

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

public class Main_BFS {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] 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 day = 1;
        while (true) {
            melt(N, M, map);

            boolean[][] 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]) continue;

                    bfs(i, j, N, M, map, visited);
                    cnt++;
                }
            }

            if (cnt == 0) {
                day = 0;
                break;
            } else if (cnt >= 2) {
                break;
            }

            day++;
        }

        System.out.println(day);
    }

    private static void melt(int N, int M, int[][] map) {
        int[][] matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) continue;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = i + dr[dir];
                    int nc = j + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == 0) matrix[i][j]++;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = Math.max(map[i][j] - matrix[i][j], 0);
            }
        }
    }

    private static void bfs(int r, int c, int N, int M, int[][] map, boolean[][] visited) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{r, c});

        visited[r][c] = true;

        while (!q.isEmpty()) {
            int[] node = q.remove();

            for (int dir = 0; dir < 4; dir++) {
                int nr = node[0] + dr[dir];
                int nc = node[1] + dc[dir];

                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                if (map[nr][nc] == 0 || visited[nr][nc]) continue;

                q.add(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }
    }

}

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

public class Main_DFS {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static int N;
    private static int M;
    private static int[][] map;
    private static boolean[][] visited;

    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());

        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 day = 1;
        while (true) {
            melt();

            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]) continue;

                    dfs(i, j);
                    cnt++;
                }
            }

            if (cnt == 0) {
                day = 0;
                break;
            } else if (cnt >= 2) {
                break;
            }

            day++;
        }

        System.out.println(day);
    }

    private static void melt() {
        int[][] matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) continue;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = i + dr[dir];
                    int nc = j + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == 0) matrix[i][j]++;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = Math.max(map[i][j] - matrix[i][j], 0);
            }
        }
    }

    private static void dfs(int r, int c) {
        visited[r][c] = true;

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if (map[nr][nc] == 0 || visited[nr][nc]) continue;

            dfs(nr, nc);
        }
    }

}

---

4. 후기

 

- BFS

- DFS