본문 바로가기
PS

[자바] 백준 2573 : 빙산 / dfs, bfs 풀이 (비슷한 문제)

by 제이._ 2023. 1. 18.

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

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을

www.acmicpc.net

골드4 난이도, 정답률 26% 문제입니다.

문제 자체는 쉬우나, 문제를 해결하기 위해서 해야 하는게 많아서 정답률이 낮아보입니다.

이 문제는 두 가지의 문제를 복합시킨 느낌입니다.

풀이 후 밑에 어떤 문제인지 적어두겠습니다!

 

문제 분석

이 문제 자체는 어떻게 풀지 이해하기 쉬운 문제입니다.

주어진 설명 그대로 0으로 채워진 칸은 바닷물이므로, 1초가 지나면 이 바닷물과 닿은 빙산은 1칸씩 줄어들게 됩니다.

만약에 빙산 주변에 바닷물(0)이 2칸 있다면 1초 후에 빙산의 높이는 {now - 2} 가 됩니다.

모든 빙산에 대해서 빙산이 2개로 쪼개지는 순간의 시간을 출력해주면 정답이 됩니다.

백준 예시에 있는 그림입니다.

그림2에서 1초가 지나면 그림 3처럼 되는데, 그림2에서는 연결된 빙산이 1개지만 / 그림3에서는 빙산이 3조각으로 분리가 됐습니다.

이렇게 1개에서 1개 이상이 됐을 때 정답을 출력해주면 됩니다.

문제 풀이

이제 문제를 분석 했으니 풀어보도록 하겠습니다.

이런 문제를 보고 바로 DFS, BFS 같은 완전탐색을 떠올릴 수 있어야합니다.

그렇게 생각한 근거는 그래프를 쭉 순회하면서 빙산의 조각도 세어야하고, 빙산도 녹여야하기 때문입니다.

이 때 적절한 알고리즘은 BFS 혹은 DFS라고 볼 수 있습니다.

문제를 풀 때 또 좋은 방법을 말씀드리자면 문제를 먼저 컴퓨터가 아닌 사람의 논리로 풀어보고 순서를 정해주고 그 순서에 맞게 코딩을 하면 됩니다.

저는 이 문제를 다음과 같이 풀어야겠다고 생각했습니다.

  1. 데이터 입력 초기화
  2. loop start
    1. if(빙산 0개 혹은 분리 시 return)
    2. 빙산의 조각 세기
    3. 빙산 녹이기
  3. 정답 출력

이 순서로 풀었고 2번 부분을 가장 신경 써서 풀었습니다.

빙산을 녹이기 전에 빙산의 조각 수를 먼저 세어 주었습니다.

이 부분은 dfs로 해결했습니다.

빙산을 녹이는 부분도 dfs로 해결할 수 있지만, 이번에는 bfs로 풀어봤습니다.

 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static int n, m;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] pos = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    private static int answer = 0;

    public static void main(String[] args) {
        // 1. 데이터 셋업
        initData();

        // 2. loop (빙산 세기, 빙산 녹이기)
        startLoop();

        // 3. 데이터 출력
        printAnswer();
    }

    private static void initData() {
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
    }

    private static void startLoop() {
        while (true) {
            // 1. 빙산의 조각 세기 (if. 빙산 0개, 혹은 분리시 return)
            int ice = countIce();
            if (ice == 0) {
                answer = 0;
                return;
            }
            if (ice >= 2) {
                return;
            }

            // 2. 빙산 녹이기
            bfsOfMeltingIce();
            answer++;
        }
    }

    private static int countIce() {
        visited = new boolean[n][m];
        int ice = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j] > 0) {
                    dfsOfCountIce(i, j);
                    ice++;
                }
            }
        }
        return ice;
    }

    private static void dfsOfCountIce(int row, int col) {
        visited[row][col] = true;

        for (int i = 0; i < pos.length; i++) {
            int nr = row + pos[i][0];
            int nc = col + pos[i][1];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && map[nr][nc] != 0 && !visited[nr][nc]) {
                dfsOfCountIce(nr, nc);
            }
        }
    }

    private static void bfsOfMeltingIce() {
        visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] > 0) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] info = queue.poll();
            int blank = 0;

            for (int i = 0; i < pos.length; i++) {
                int nr = info[0] + pos[i][0];
                int nc = info[1] + pos[i][1];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] == 0) {
                    blank++;
                }
            }

            if (map[info[0]][info[1]] - blank < 0) {
                map[info[0]][info[1]] = 0;
            } else {
                map[info[0]][info[1]] -= blank;
            }
        }
    }

    private static void printAnswer() {
        System.out.println(answer);
    }
}
 
 

비슷한 문제

이 문제는 두 가지의 문제가 섞인 것 같다고 위에서 언급했습니다.

 

먼저 위 문제에서 빙산을 세는 부분은 [백준 2667 : 단지번호붙이기] 문제와 유사합니다.

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

또한 위 문제에서 빙산을 녹이는 부분은 [백준 2636 : 치즈] 문제와 유사합니다.

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

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net