백준 16940. BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

 

우선 내가 푼 방법이다.

이 방법은 처음에 시간초과 날것 같았는데 다른 방법이 떠오르지 않아서 그냥 해봤는데 통과했다.

시간은 1700ms 대로 이 문제는 2s 제한이므로 아슬아슬하게 통과했다.

 

내가 푼 방법은 그냥 bfs 알고리즘 그대로 따라가 보는 것이다.

현재 노드에서 이동할수 있는 다음 노드들을 모아서, 그 중에 내가 탐색해야하는 다음 방문순서가 있으면 가고, 없으면 실패처리하는 방식이다.

 

 

---

다음 방법은 훨씬 효율적인 방법이다.

이 방법은 입력으로 주어진 bfs 탐색 순서를 기반으로 주어진 그래프의 순서를 미리 맞춰놓는 방법이다.

 

만약 주어진 bfs 탐색 순서가 {1, 3, 2, 4} 라고 하고 그래프가 다음과 같다.

     

            1

         /      \

      2         3

   /

4

 

그러면 그냥 bfs 탐색을 수행하면 왼쪽 노드부터 방문하도록 입력받았다고 치면 1 - 2 - 3 - 4 로 방문한다.

우리가 할 일은 bfs 탐색 순서에 맞춰서 미리 그래프를 조작해 놓는것이다. 

 

즉 다음과 같은 모양이 되도록 미리 바꿔놓는 것이다. 

 

            1

         /      \

      3         2

   /

4

 

그래프가 이렇다면 그냥 bfs 를 돌리면 1 - 3 - 2 - 4 로 방문할 것이다. 

 

 

그렇다면 그래프를 어떻게 위와 같이 바꿀수 있을까

각 노드와 연결된 노드의 순서를 정렬하면 되는데, 정렬할때 기준을 bfs 탐색 순서에 따라 정렬하면 된다.

bfs 탐색 순서 = {1, 3, 2, 4} 이므로 예를들어 1에 연결된 노드는 2와 3인데, 탐색 순서에서 3이 2보다 앞에 있기 때문에 위 그래프처럼 정렬될 것이다.