[백준 3197] 백조의 호수 (Java)

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

3197번: 백조의 호수

 

풀이

문제를 처음 보고 다음과 같은 방법으로 시도를 했다.

1. BFS로 얼음을 녹이고 map을 업데이트 시킨다.

2. 해당 map에서 두 백조가 만날 수 있는지 BFS 탐색을 시도한다.

3. 만날 수 없다면 day++를 하고 1, 2번을 반복한다.

4. 만나는 경우에 day를 출력한다.

 

위 방법으로는 시간 초과가 발생할 수 있다.

예를 들어 백조가 만날 수 있는 날이 n일차라면 (이 n이 아주 크다면) 1일부터 차례로 탐색하게 되면 시간 복잡도가 O(n)이 된다.

 

이를 이진 탐색으로 변경해보자.

0 < k < n 이라고 할 때, k일차의 경우 백조가 만날 수 없다면 당연히 k-1일과 같이 k일 이전 역시 만날 수 없으니 k일 이후로만 고려해도 되기 때문에 시간복잡도는 O(log n)으로 단축된다.

 

이진 탐색을 시도하기 위해서는 각 얼음이 몇 일차에 녹는지 알아야한다.

각 얼음이 언제 깨지는 지 나타내는 int[][] melt를 생성해서 기록한다. (BFS를 이용하여 기록)

 

최종 구현된 코드의 접근 순서는 다음과 같다.

1. melt배열에 각 얼음이 깨지는 날짜를 기록한다. (melt함수, BFS)

   - 이 때 모든 얼음이 깨지는 마지막 날을 기록해둔다.

2. 이진 탐색을 이용해 백조가 만날 수 있는 최소의 날짜를 찾는다.

   - left는 0, right는 모든 얼음이 깨지는 마지막 날로 두고 시작한다.

   - left와 right의 중간값인 mid일차에 백조가 만난다면 최솟값을 찾기위해 이진 탐색을 계속 진행한다.

   - left와 right의 중간값인 mid일차에 백조가 만나지 못 한다면 mid일 이하의 날에는 무조건 백조가 만나지 않기 때문에 효율적으로 거를 수 있다.

3. 이진 탐색으로 나온 중간 값을 limit로 두고 두 백조 간 BFS 탐색 시 경로는 limit보다 작거나 같은 경우에만 이동이 가능하도록하여 접근 유무를 결정한다.

 

 

코드

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

public class Main {

    private static int R;
    private static int C;
    private static char[][] map;
    private static int[][] melt;
    private static int day;
    private static int[] x_move = {1, 0, -1, 0};
    private static int[] y_move = {0, 1, 0, -1};

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

        R = Integer.parseInt(firstLine.split(" ")[0]);
        C = Integer.parseInt(firstLine.split(" ")[1]);

        map = new char[R][C];
        List<Point> swan = new ArrayList<>();

        for (int i = 0; i < R; i++) {
            String input = in.readLine();

            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);

                if (map[i][j] == 'L') {
                    swan.add(new Point(i, j));
                }
            }
        }

        in.close();

        melt = melt();

        int left = 0;
        int right = day;
        int min = Integer.MAX_VALUE;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (isReachable(swan.get(0), swan.get(1), mid)) {
                min = Math.min(min, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(min);
    }

    private static boolean isReachable(Point point1, Point point2, int limit) {
        boolean[][] visited = new boolean[R][C];

        Queue<Point> queue = new LinkedList<>();
        queue.add(point1);
        visited[point1.x][point2.y] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int k = 0; k < 4; k++) {
                int new_x = point.x + x_move[k];
                int new_y = point.y + y_move[k];
                if (inArea(new_x, new_y) && !visited[new_x][new_y] && melt[new_x][new_y] <= limit) {
                    visited[new_x][new_y] = true;

                    if (new_x == point2.x && new_y == point2.y) {
                        return true;
                    }

                    queue.offer(new Point(new_x, new_y));
                }
            }
        }

        return false;
    }

    private static int[][] melt() {
        boolean[][] visited = new boolean[R][C];
        int[][] melt = new int[R][C];

        Queue<Point> queue = new LinkedList<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L' || map[i][j] == '.') {
                    queue.offer(new Point(i, j));
                    visited[i][j] = true;
                }
            }
        }

        day = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            day++;

            for (int i = 0; i < size; i++) {
                Point point = queue.poll();

                for (int j = 0; j < 4; j++) {
                    int new_x = point.x + x_move[j];
                    int new_y = point.y + y_move[j];
                    if (inArea(new_x, new_y) && !visited[new_x][new_y] && map[new_x][new_y] == 'X') {
                        melt[new_x][new_y] = day;
                        visited[new_x][new_y] = true;

                        queue.offer(new Point(new_x, new_y));
                    }
                }
            }
        }

        return melt;
    }

    private static boolean inArea(int x, int y) {
        return x >= 0 && y >= 0 && x < R && y < C;
    }

    static class Point {
        int x;
        int y;

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

 

[참고]

https://exponential-e.tistory.com/25