[BOJ] 백준 3197번 : 백조의 호수

date

Jun 26, 2023

slug

boj-3197

author

status

Public

문제링크

3197번: 백조의 호수

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

⭐️ 이전 결과를 큐에 저장하여 그곳에서부터 다시 BFS를 수행한다면 중복되는 탐색을 줄일 수 있다!

전체적인 풀이는 치즈(백준 2636)와 비슷하지만, 녹는 과정 전에 두 백조가 서로 만날 수 있는지 확인하는 과정이 필요함

이때 백조가 만나는지 확인하는 것을 일반적인 BFS/DFS로 구현할 시 시간초과가 발생함!!

⇒ 최악의 경우 1500 * 1500 * 1499(얼음이 다 녹는 최악의 일수)의 시간복잡도

따라서 BFS를 돌 때 처음부터 도는 것이 아니고 이전에 막혔던 마지막 지점에서부터 시작

두개의 큐를 준비

큐1 : BFS 진행하는 큐(즉, 물과 백조일 때만 저장하는 큐, 여기서 빼서 전진 탐색)

큐2 : BFS 진행 중 만난 벽을 저장하는 큐(얼음 녹일 때 이 얼음들은 물로 변할 것이기 때문에 이곳에서부터 BFS를 시작할 것임)

두 마리의 백조가 서로 만나는지 확인하는 함수


private static boolean swanCanMeet() {
        Queue<Ice> nextQueue = new LinkedList<>();
        while(!pathQueue.isEmpty()) {
            Ice ice = pathQueue.poll();

            for (int k = 0; k < 4; k++) {
                int ny = ice.r + dy[k];
                int nx = ice.c + dx[k];
                if (ny < 0 || nx < 0 || ny >= R || nx >= C || swanVisited[ny][nx]) continue;
                if (ny == swan[1][0] && nx == swan[1][1]) {
                    return true;
                }

                swanVisited[ny][nx] = true;
                if (map[ny][nx] == 1) {
                    nextQueue.add(new Ice(ny, nx));
                } else {
                    pathQueue.add(new Ice(ny, nx));
                }
            }
        }

        pathQueue = nextQueue;
        return false;

    }