2 - 2. BFS 예제 (3197번: 백조의 호수)

백준 3197번(백조의 호수)

 

 

 

이 문제.. 제가 처음 풀때 정말 몇번이나 시간초과로 고생했던 기억이 있네요.

BFS라고 분류 되어있지만 일반적인 BFS는 해결이 불가능합니다.

 

난이도가 꽤 높은 편인데 이 문제를 가져온 이유는 우리가 이제껏 공부한 내용으로 해결이 가능하기 때문입니다.

제가 아는 바에 의하면 해결법이 2가지가 존재합니다.

 

제가 해결한 방법은 'BFS + Binary Search' 입니다.

다른 방법으로는 'BFS + 서로소 집합(Disjoint Set 또는 Union find)'로 해결이 가능하다고 합니다.

후자의 경우엔 제가 아직도 연습이 많이 필요해서 그에 대한 설명은 못 드릴거 같아요. ㅠㅠ

열심히... 할게요(?)

 

 

문제에서 크게 신경 쓸 내용은 없습니다.

기본적인 BFS 문제인데 빙하가 테두리부터 하루씩 녹아 내린다는 점.

그리고 그 빙하가 녹아서 두 백조가 만날 수 있는 최소 일수를 찾아야 한다는 점.

결국 우리는 이 두가지만을 고민해 보면됩니다.

 

어떻게 하면 문제를 조금 더 직관적으로, 잘못된 답이 나와도 바로바로 디버깅 할 수 있을까요?

 

첫째로, 

인접행렬로 맵이 주어집니다.

따라서, 저는 처음에 빙하가 녹는 날짜에 대한 정보를 배열에 따로 저장하자 라는 생각을 했습니다.

그리고 해당 배열을 출력해 보면 답이 나오진 않아도 언제가 만날 수 있는 기간 중 최소인지 알기 쉽겠죠.

단, 두마리가 만나는 날짜니까 두 백조의 위치 및 중간에 존재하는 바다에서 상대적으로 빙하를 녹여가며 시간을 측정 해야합니다.

 

둘째로,

이 최소 일수를 하나씩 넣어보면서 탐색한다면?

물론 답이 나오긴 합니다.

하지만, 최악의 경우를 생각해 볼게요. (실제로 해당 데이터도 문제에 존재합니다.)

중간은 모두 빙하라고 가정 했을때 아래의 그림과 같은 경우에 녹는데 몇일이 걸릴까요?

 

 

잘은 모르겠지만, 대각선으로 거리가 적어도 1000 * 2 정도는 넘어갑니다. (가로 + 세로, 이정도니까.. 대충잡아서)

이를 반으로 나누면 1000일 쯤은 되어야 만날 수 있습니다.

그 1000일 이란건 눈엔 보이지만 컴퓨터가 각 케이스마다 알아서 그것이 최소라고 인식하긴 어렵습니다.

따라서 N일이라는 결과가 나오면 1 ~ N일까지 모두 반복문을 돌려보며 확인해보는 수 밖에 없죠.

 

그러면 걸리는 시간은 1500 * 1500 * 1000 = 2,250,000,000 (약 20억) 입니다.

기준 제한 1초(약 1억회)를 훨씬 웃도는 결과 입니다.

(저도 잘 모르고 풀었다가 저런식으로 시간초과를 받았었죠..ㅠ)

 

 

그럼 위의 방법은 안된다는것을 알았는데, 

아까 제가 '이분탐색을 사용 할 것이다.' 라고 말씀드렸잖아요.

여기서 이미 정렬된 고정 값은 존재하는지 찾아봐야죠.

녹는 일수는 1 ~ N까지 일정하게 증가하니까, 이를 기준 삼아 이분탐색을 해도 되겠네요.

 

그럼 녹는 일수로 이분탐색을 한다면 그 결과가 일정하게 나오는지도 생각 해봐야합니다.

즉, 0 < M < K < N 이러한 경우에, 최소 날짜는 0 이고 최대 날짜는 N 입니다.

근데 만약 탐색 중에 M이란 날짜에 만날 수 있다는 것이 확인이 되었는데 K란 날짜에 못만나는 경우가 있을까요?

 

당연하게도 불가능합니다.

빙하는 날짜가 지날수록 계속 녹는데, K일이 되었다고 갑자기 빙하가 생겨나진 않으니까요.

따라서 이분탐색이 적용이 가능합니다.

 

그래서 앞으로 아래와 같은 순서로 문제를 해결해 나가려고 합니다.

1. 백조의 위치 및 중간에 존재하는 바다를 체크해서 이때 얼음이 녹는 시간을 melt 배열에 저장합니다.
1. 처음부터 바다라면 0이라는 값이 들어갑니다.
2. 1에서 BFS는 전에 했던 토마토 기억하시죠? 그 방식대로 합니다.
1. 즉 바다의 위치 및 백조의 위치를 미리 큐에 담고
2. 각 위치에서 탐색하며 퍼트려 빙하가 존재하면 일수를 하나씩 늘려주며 넣어줍니다.
3. 단, 큐에 들어있는것을 우선적으로 먼저 돌립니다.
4. 그렇게 해야 테두리부터 1일씩 차근차근 값을 담아 줄 수 있겠죠.
3. 그리고 이 배열에서 최댓값을 받아옵니다.
1. 이분탐색하기 위해선 구간이 필요하니까 당연하겠죠.
2. 그래서 0을 left, 최댓값을 right로 저장합니다.
4. 저장한 값으로 이분탐색을 실행합니다.
1. 이때 이분탐색 알고리즘 내부에서 BFS를 다시 실행합니다.
2. 이번의 BFS는 이분탐색에서 나온 mid의 값보다 작거나 같은 값을 모두 0으로 치부하고 탐색합니다.
3. 즉 mid는 어떤 기준이되는 날짜이며, 이 날짜보다 작거나 같은 날짜는 이미 녹은 상태라고 여기게 되는것이죠.
5. 이렇게 돌리다가 백조가 만나면 참, 못 만나면 거짓을 반환하고 만날때마다 날짜의 최소를 찾아줍니다.

 

 

글로만 보시면 이해가 조금 힘들수도 있으니, 그림도 준비해봤습니다.

색은 아까 위의 표와 같습니다. 노란색이 백조, 연한 파랑이 빙하, 진한 파랑이 바다입니다.

 

 

 

실제로 데이터가 0이 되는것은 아니지만 조건문에 의해 이동 가능하다라고 여겨지는 것 입니다.

melt[row][col] <= mid 이러한 조건을 만들어 조건에 맞다면 움직이게 말이죠.

위의 경우엔 3일만에 백조들이 만나겠네요.

 

그래서 우리는 총 BFS 2회와 Binary Search 1회의 코드를 사용하게 됩니다.

아래는 얼음이 녹는 날짜를 저장하는 초기화 메소드입니다.

 

 

3197번 BFS 메소드 (init: 빙하가 녹는 날짜 저장)

private static int[][] init(int N, int M, int[][] arr, char[][] graph){
    int counts = 1;
    boolean[][] isVisited = new boolean[N][M];
        
    Queue<Point> q = new LinkedList<>();
        
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(graph[i][j] == 'L' || graph[i][j] == '.') {        // 녹기 시작할 기준부터 큐에 저장
                q.offer(new Point(i, j));
                isVisited[i][j] = true;
            }
        }
    }
        
    while(!q.isEmpty()) {
        int size = q.size();
            
        for(int i = 0; i < size; i++) {            // 테두리부터(1일차) 녹여가야하므로 큐내에 들어있는 것들만 우선적으로 돌림
            Point current = q.poll();
                
            for(final int[] DIRECTION: DIRECTIONS) {
                int nextRow = current.row + DIRECTION[ROW];
                int nextCol = current.col + DIRECTION[COL];
                    
                if(nextRow >= 0 && nextCol >= 0 && nextRow < N && nextCol < M) {
                    if(!isVisited[nextRow][nextCol] && graph[nextRow][nextCol] != 'L') {
                        arr[nextRow][nextCol] = counts;
                        isVisited[nextRow][nextCol] = true;
                            
                        q.offer(new Point(nextRow, nextCol));
                    }
                }
            }
        }
        
        counts++;
    }
 
    return arr;
}

 

 

3197번 BinarySearch 메소드 (기준 날짜 정하기)

while(left <= right) {
    int mid = (left + right) / 2;
    boolean attaced = canMeet(R, C, melt, mid, start);
            
    if(!attaced) {                        // 안만난 경우 일수를 증가
        left = mid + 1;
    }
    else {                                // 만난 경우 최소 일수를 찾음
        if(min > mid) min = mid;
        right = mid - 1;
    }
}

 

 

3197번 BFS 메소드 (canMeet: 기준 날짜를 통해 만날 수 있는지 확인)

private static boolean canMeet(int N, int M, int[][] arr, int limits, Point[] start) {
    boolean[][] isVisited = new boolean[N][M];
 
    Queue<Point> q = new LinkedList<>();
    q.offer(new Point(start[0].row, start[0].col));
        
    isVisited[start[0].row][start[0].col] = true;
        
    while(!q.isEmpty()) {
        Point current = q.poll();
            
        for(final int[] DIRECTION: DIRECTIONS) {
            int nextRow = current.row + DIRECTION[ROW];
            int nextCol = current.col + DIRECTION[COL];
                
            if(nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M) {
                if(!isVisited[nextRow][nextCol] && arr[nextRow][nextCol] <= limits) {
                    isVisited[nextRow][nextCol] = true;
                        
                    if(nextRow == start[1].row && nextCol == start[1].col) return true;
                        
                    q.offer(new Point(nextRow, nextCol));
                }
            }
        }
    }
    
    return false;
}

 

3197번 전체 코드

package breadth_first_search;
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
 
/**
 * 
 *     @author minchoba
 *    백준 3197번: 백조의 호수
 *
 *    @see https://www.acmicpc.net/problem/3197/
 *
 */
public class Boj3197 {
    private static final int[][] DIRECTIONS = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    private static final int ROW = 0;
    private static final int COL = 1;
 
    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        int R = in.readInt();
        int C = in.readInt();
        
        Point[] start = new Point[2];
        int idx = 0;
        
        int[][] melt = new int[R][C];
        char[][] map = new char[R][C];
        
        for (int i = 0; i < R; i++) {
            String line = in.readString();
            for(int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
                
                if(map[i][j] == 'L') {
                    start[idx] = new Point(i, j);
                    idx++;
                }
            }
        }
        
        melt = init(R, C, melt, map);                // 얼음이 녹는 시간 측정
        
        int left = 0, right = 0, min = Integer.MAX_VALUE;
        
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(melt[i][j] > right) right = melt[i][j];
            }
        }
 
        while(left <= right) {
            int mid = (left + right) / 2;
            boolean attaced = canMeet(R, C, melt, mid, start);
            
            if(!attaced) {                    // 안만난 경우 일수를 증가
                left = mid + 1;
            }
            else {                            // 만난 경우 최소 일수를 찾음
                if(min > mid) min = mid;
                right = mid - 1;
            }
        }
        
        System.out.println(min);
    }
 
    private static class Point {
        int row;
        int col;
 
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    private static int[][] init(int N, int M, int[][] arr, char[][] graph){
        int counts = 1;
        boolean[][] isVisited = new boolean[N][M];
        
        Queue<Point> q = new LinkedList<>();
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(graph[i][j] == 'L' || graph[i][j] == '.') {        // 녹기 시작할 기준부터 큐에 저장
                    q.offer(new Point(i, j));
                    isVisited[i][j] = true;
                }
            }
        }
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            for(int i = 0; i < size; i++) {                    // 테두리부터(1일차) 녹여가야하므로 큐내에 들어있는 것들만 우선적으로 돌림
                Point current = q.poll();
                
                for(final int[] DIRECTION: DIRECTIONS) {
                    int nextRow = current.row + DIRECTION[ROW];
                    int nextCol = current.col + DIRECTION[COL];
                    
                    if(nextRow >= 0 && nextCol >= 0 && nextRow < N && nextCol < M) {
                        if(!isVisited[nextRow][nextCol] && graph[nextRow][nextCol] != 'L') {
                            arr[nextRow][nextCol] = counts;
                            isVisited[nextRow][nextCol] = true;
                            
                            q.offer(new Point(nextRow, nextCol));
                        }
                    }
                }
            }
            
            counts++;
        }
        
        return arr;
    }
    
    private static boolean canMeet(int N, int M, int[][] arr, int limits, Point[] start) {
        boolean[][] isVisited = new boolean[N][M];
 
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(start[0].row, start[0].col));
        
        isVisited[start[0].row][start[0].col] = true;
        
        while(!q.isEmpty()) {
            Point current = q.poll();
            
            for(final int[] DIRECTION: DIRECTIONS) {
                int nextRow = current.row + DIRECTION[ROW];
                int nextCol = current.col + DIRECTION[COL];
                
                if(nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M) {
                    if(!isVisited[nextRow][nextCol] && arr[nextRow][nextCol] <= limits) {
                        isVisited[nextRow][nextCol] = true;
                        
                        if(nextRow == start[1].row && nextCol == start[1].col) return true;
                        
                        q.offer(new Point(nextRow, nextCol));
                    }
                }
            }
        }
        
        return false;
    }
}
 

 

 

입력으로 사용한 InputReader는 fast I/O를 위한 클래스 입니다.

일반적인 BufferedReader 사용하셔도 무방하고, 괜히 쓸데없이 코드가 길어져서 해당 내용은 지웠습니다.

 

해당 코드의 시간 복잡도는 BFS: O(H * W * log(H * W)) = 2,250,000 * 약 20 = 약 50,000,000 정도 나오겠네요.

아래에서도 보이다시피 1500ms 정도... 사실 위에서 말씀드렸던 서로소 집합을 이용해 푼다면 훨씬 빠를텐데 약간 아쉽네요.

 

 

제출 결과

 

 

고통의 흔적이 고스란히 보입니다..ㅎㅎ 여기까지입니다.

 

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

 

 

 

문제의 저작권은 백준 온라인 저지에 있습니다.