실패한 경우는 같은 층을 큐에 여러 번 집어넣을 수 있습니다.

예를 들어 어떤 두 층 a, b에 대해 s층에서 a층까지 최소횟수로 가는 경우의 수가 5가지고, a층에서 b층까지 최소횟수로 가는 경우의 수가 5가지이며, s층에서 b층으로 최소횟수로 가려면 a층을 거쳐가야 한다고 해봅시다. 그러면 s층에서 b층까지 최소횟수로 가는 경우의 수는 5*5 = 25가지입니다.

그런데 위 코드의 1번 케이스대로 하면, 큐에서 a가 나오기 전까지 a로 도달할 수 있는 모든 경우의 수에 대해 한 번씩 큐에 a를 집어넣게 됩니다. 즉, 처음으로 a를 꺼내기 직전 큐에는 a가 총 5개 들어있습니다. 이제는 b에 대해서 유사한 일이 벌어지는데, 각각의 a에 대해 b로 갈 수 있는 경로의 수는 5개이므로, 5개의 a에 대해 각각 b가 5번씩 들어가집니다. 결과적으로 큐에는 b가 25번 들어갑니다.

이와 같은 경우가 연쇄적으로 있을 경우, 큐에 같은 정점이 들어가는 횟수가 지수적으로 증가하게 됩니다. BFS는 그 특성상 도착지점에 도달하기 전까지 그보다 짧은 길이의 경로는 전부 탐색하는데, 이는 큐에서 값을 꺼냄으로써 이뤄집니다. 즉, 큐에 들어가는 원소의 수가 기하급수적으로 늘어나면, BFS는 큐에서 그 수많은 수를 다 꺼낼 때까지 종료하지 않습니다. 이때문에 1번 케이스는 시간초과가 납니다. 시간초과가 아니었어도 극단적으로 길어진 큐에 의해 메모리초과가 발생했을 겁니다.

정리하면, 하나의 값이 큐에 중복되어 들어갈 수 있기 때문에 그러한 문제가 발생하는 겁니다.

2번 케이스의 경우는 큐에 넣을 때 방문 체크를 함으로써, 한 번 큐에 들어갔던 값은 다시는 큐에 들어가지 않게 됩니다. 이 덕분에 층수 F에 대해 O(F) 안에 탐색이 종료될 수 있게 됩니다.