BOJ P5 3197 백조의 호수 BFS+이분탐색 JAVA

3197번: 백조의 호수

---

문제 읽기

처음에 문제를 읽었을 때는 일반적인 시뮬레이션 문제 같았다. 단순하게 생각하면 다음과 같은 구조로 풀이를 할 수 있을 것이다.

1. 모든 판을 순회하며 물과 인접한 얼음에 없앤다는 표식을 남긴다
2. 다시 모든 판을 순회하며 표식이 있는 얼음을 녹여 물로 만든다
3. 위 과정이 끝났으면 백조 한 마리의 위치에서 BFS를 수행하여, 물로만 이동했을 때 다른 백조까지 도달하는 지 파악한다
4. 두 백조가 만났다면 끝내고, 만나지 않았지만 1-3 과정을 반복한다.

 

하지만 플레 문제가 이렇게 단순할 리가 없다..!!!

의심은 했지만 한 번 고대로 풀어서 내봤더니 역시나 시간초과가 나왔다.

사실 시간 복잡도 한 번 계산하고 들어갔는데, 매우 중요한 걸 실수했다.

 

1 → RC4 = 150015004 = 9,000,000(9백만)

2 → RC = 15001500 = 2250000(약 2백만)

3 → RC = 15001500 = 2250000(약 2백만)

 

이렇게만 생각했는데 4번을 빼먹었다.

 

4 → 얼음이 다 녹는 시간. 최악의 경우 1500*루트2 ( = 한 변 1500인 정사각형 대각선 길이) = 3000

 

4번까지 해주면, (약 1300만) * 3000 = 39000000000(390억)

절대 안 됨@@

 

근데 도저히 방법은 떠오르지 않아서 질문 게시판 고전 글을 참고해봤다.

글 읽기 - 시간초과가 나는데 해결방법이 안떠오릅니다

Point 1

Point 2

 

풀이 방법이 여러가지인 거 같은데, 일단 이 게시판에 있는 풀이로 처음으로 해결해서, 이 내용을 포스팅 해보겠다.

---

문제 풀이

풀이에 필요한 알고리즘을 요약하자면 BFS + 이분탐색이다.

1. BFS - 얼음 녹이는 시간 구하기

1. 입력 받을 때 모든 물의 좌표를 water라는 큐에 다 넣는다.
2. bfs를 돌면서 인접한 얼음에 대해 depth+1을 해주면서 새로운 배열에 그 값을 써준다.
   1. 다음과 같은 전처리된 시간들을 얻을 수 있다.
   2. 이 시간들이 의미하는 바는, 해당 위치의 얼음이 녹는 시간이 된다. 이를 이용하여 백조가 언제 만날 수 있는지 확인할 수 있다.

💡 시간 복잡도 계산하기

내가 처음에 맘대로 풀었던 시뮬레이션 방식은, N이 작을 때만 가능하다. 이 문제의 경우에는 N이 너무 크고, 경우가 너무 많아지기 때문에 시뮬레이션이 거의 불가능한 것이다. (시간, 메모리 문제..)

그래서 이 풀이는 시뮬레이션해서 얼음을 시간에 따라 녹이는 게 아니라, 얼음이 녹을 시간을 한 번의 BFS로 다 구해버리는 것이다. 이게 바로 전처리이다.

이 한 번의 전처리를 끝내놓으면, 위의 4번 반복문(시뮬레이션)을 돌 필요가 없어지고, 오직 두 마리의 백조가 만날 수 있는 지만 파악하면 끝이다.

 

 

2. 이분탐색 + BFS - 백조 만나기

1. 이분탐색을 적용한다 (0~3000사이의 값)
   1. 가운데 시간인 mid 시간에 백조 하나의 위치부터 bfs를 돌린다
      1. 만났으면
         1. 이전 시간에 만났을 수도 있으니 (start, mid)를 다시 돌린다
      2. 안 만났으면
         1. 무조건 이후 시간에 만나는 것이니 (mid+1, end)를 다시 돌린다.
   2. start ≥ end 되면 end를 리턴한다.

💡 시간복잡도 계산하기

여기서 백조가 만나는 걸 확인하려면 BFS를 사용하는데, 위에서 구했듯이 BFS의 시간 복잡도는 약 200만, 얼음이 다 녹는데 최대 3000시간이 걸리므로 여기에 3000을 곱하면 6,000,000,000 = 60억이다. 따라서 시간 초과가 나기 때문에 이분탐색을 적용한 것이다.

이분 탐색을 적용하면 200만 * log2(3000)이므로 약 173,149 = 10만 번의 연산이 발생한다. 따라서 이분탐색 + BFS가 가능한 것이다.

 

 

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_P5_3197_백조의_호수_ver1_bfs_이분탐색 {
    static class Pos{
        int r, c;
        int depth;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
        public Pos(int r, int c, int depth){
            this.r = r;
            this.c = c;
            this.depth = depth;
        }
    }
    static int R, C;
    static char[][] map;
    static int[][] days;
    static Queue<Pos> water;
    static int startR = -1, startC = -1;
    static int endR = -1, endC = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        days = new int[R][C];
        water = new ArrayDeque<>();
        for (int i = 0; i < R; i++){
            String line = in.readLine();
            int j = 0;
            for (char c : line.toCharArray()){
                if (c == 'L'){
                    if (startR == -1){
                        startR = i;
                        startC = j;
                    }
                    else{
                        endR = i;
                        endC = j;
                    }
                    water.offer(new Pos(i, j, 0));
                }
                else if (c == '.'){
                    water.offer(new Pos(i, j, 0));
                }
                map[i][j++] = c;
            }
        }

        //logic
        //1. 빙산이 언제 녹을 지 전처리 -> bfs
        melting();
        for (int i = 0; i < R; i++){
            System.out.println(Arrays.toString(days[i]));
        }

        //2. 백조 bfs 이분탐색 수행
        int day = binarySearch(0, 3000);

        System.out.println(day);
    }

    private static int binarySearch(int start, int end) {
        if (start >= end) return end;

        int mid = (start + end) / 2;
        if (bfs(mid)){ //만났다 - 왼쪽
            end = mid;
        }
        else{ //못만났다 - 오른쪽 부분
            start = mid + 1;
        }
        return binarySearch(start, end);
    }

    private static void melting() {
        boolean[][] visited = new boolean[R][C];
        //얼음이고, 방문하지 않은 곳이면 방문하면서 숫자를 체크

        while(!water.isEmpty()){
            Pos cur = water.poll();

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] || map[nr][nc] != 'X') continue;

                visited[nr][nc] = true;
                water.offer(new Pos(nr, nc, cur.depth+1));
                days[nr][nc] = cur.depth+1;
            }
        }
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    private static boolean bfs(int cutline) {
        Queue<Pos> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[R][C];

        q.offer(new Pos(startR, startC));
        visited[startR][startC] = true;

        while(!q.isEmpty()){
            Pos cur = q.poll();

            if (cur.r == endR && cur.c == endC) return true;

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] || days[nr][nc] > cutline) continue;

                visited[nr][nc] = true;
                q.offer(new Pos(nr, nc));
            }
        }
        return false;
    }
}