안녕하세요!

코드에서 고쳐야 하는 부분 두 가지를 찾았습니다.

1) temp 값이 100,001 이 될 경우 배열의 범위를 벗어날 수 있습니다.

visited 배열의 원소의 개수는 100,001 이므로 인덱스는 0 ~ 100,000 까지 있습니다. 여기서 temp 값이 100,001이 될 경우 visited[100001] 을 참조하게 될 수도 있을 것입니다.

어차피 문제에서는 0 ~ 100,000 이 범위이니 visited[100001] 은 찾아볼 이유도 없고 찾아봐서도 안 되는 인덱스이니 범위를 아래 코드와 같이 수정해 줍시다. 이렇게 하면 IndexError는 해결됩니다.

2) BFS에서 간선의 길이가 0, 1인데, 아무런 우선순위 없이 BFS가 수행되고 있습니다.

이게 대체 무슨 뜻이냐... 라고 물으신다면, 위의 예시를 한 번 봅시다. 큐에는 현재 거리가 5인 원소와 거리가 3인 원소가 담겨 있습니다. 두 원소는 모두 좌표가 목적지를 가리킨다고 가정해 봅시다(즉, 두 원소 모두 curr_num이 k, 동생을 찾는 경우입니다).

이 경우 답은 3이 되어야 합니다. 거리가 5인 상태에서 동생을 찾는 경우가 나오고, 또 거리가 3인 상태에서 동생을 찾는 경우가 나온다면 더 거리가 가까운(= 시도 횟수가 적은) 거리 3이 당연히 답이 되어야 합니다.

하지만 해당 큐에서는 거리가 5인 원소가 먼저 pop되므로 답은 5가 출력되게 됩니다. 즉, 틀리는 경우가 생기게 됩니다. 질문자님의 코드에서는 이런 경우가 생길 수 있습니다.

아니, BFS가 최단 거리를 찾는 데 쓰이는 알고리즘 아니냐, 무조건 거리가 가까운 원소가 먼저 처리되는 게 보장되니 저런 경우는 나올 수 없는 경우 아니냐, 라고 물으실 수 있지만, 그건 어디까지나 모든 간선의 길이가 1인 경우 (= 모든 간선의 길이가 동일한 경우) 에나 보장됩니다. 간선의 길이가 제각각인 경우 BFS를 사용할 수 없고 다익스트라나 플로이드-와샬 등의 최단거리 알고리즘을 사용하여야 합니다.

하지만 해당 문제는 간선의 길이가 1, 0인 경우만 존재합니다. 앞뒤로 한 칸씩 이동해 count+=1 이 되는 경우가 바로 간선의 길이가 1인 경우, 순간이동을 해 count 값이 변하지 않는 경우가 간선의 길이가 0인 경우입니다. 이 경우에는 BFS를 사용할 수 있습니다. 그러나 그대로 사용할 수는 없고, 0-1 BFS라는 것을 사용하여야 합니다. 0-1 BFS는 일반적인 BFS와 비슷하지만, 간선의 길이가 0인 경우를 1인 경우보다 우선순위가 높은 것으로 보고 항상 간선의 길이가 0인 경우를 큐의 맨 앞에 추가시키는 방식이 다른 점입니다. 이해가 안 될 수 있으니 예를 들어 봅시다.

지금 처리되고 있는 원소는 거리가 4인 원소이고, 큐에는 거리가 5인 원소가 하나 남아 있습니다. 곧 추가될 원소는 지금 처리하고 있는 거리가 4인 원소에서 새롭게 추가될 원소를 의미합니다. 순간이동을 하는 경우인 '거리 4' 원소, 그냥 앞뒤로 이동하는 경우인 '거리 5' 원소가 있습니다. 보라색으로 표시한 '거리 4' 원소는 동생과 만나는 좌표가 담겨 있다고 가정해 봅시다.

이 경우 일반 BFS처럼 원소들을 추가시킬 경우 '거리 4' 인 원소가 이미 큐에 담겨 있는 '거리 5' 원소 뒤에 추가되게 됩니다. 즉, '거리 5' 원소보다 늦게 처리됩니다. 여기서 만약 '거리 5' 원소 또한 동생과 만나는 경우라면 4가 답이 되어야 하는데, 5가 답이 되는 상황이 옵니다. 이래서는 안 됩니다. 0-1 BFS는 이런 상황을 막기 위해 우선순위에 따라 처리합니다.

위의 그림은 바로 0-1 BFS를 적용시킨 큐입니다. 보라색으로 표시한 '거리 4' 원소는 순간이동을 했으므로 간선의 길이가 0인 경우입니다. 이 경우 우선순위가 높으므로, '거리 4' 원소는 큐의 앞에 추가됩니다. queue.appendleft()를 적용했다는 뜻입니다. 노란색으로 표시한 '거리 5' 원소는 평범하게 앞뒤로 이동한 경우입니다. 즉 간선의 길이가 1인 경우입니다. 이 경우 우선순위가 높지 않으므로 평소대로 큐의 뒤에 추가합니다. queue.append()를 적용했다는 뜻입니다. 이렇게 우선순위를 우선으로 한 이유는 평범하게 이동하는 경우보다 순간이동을 하는 경우를 더 우선적으로 처리해야 거리가 더 짧은 원소가 후순위에 배정되는 일이 없기 때문입니다. 이렇게 하면 '거리 4' 원소가 동생과 만나는 경우 가장 우선적으로 처리되어 4가 답이 되는 상황이 됩니다.

따라서 고쳐야 하는 부분 두 가지를 요약하면,

1) temp 값 범위를 고쳐주세요.

2) 0-1 BFS가 구현되도록 순간이동을 하는 경우에는 큐의 앞에 원소를 추가해 주세요.

입니다.

만약 0-1 BFS가 이해가 안 되셨다면 인터넷에 꼭 0-1 BFS를 검색해 보셨으면 좋겠습니다. 문제 해결에 도움이 되었기를 바랍니다. 

와... 친절한 설명 정말 감사합니다 ㅠㅠ

간선의 비용이 같은 문제들만 풀다보니 설명해주신 2번 문제점을 생각지도 못했었네요 ...

덕분에 간선의 비용이 다를 경우 어떻게 문제를 풀어야 할지 생각해 볼 수 있었습니다.

저도 남들에게 친절하게 알려줄 수 있을 정도의 실력이 되면 좋겠네요!  멋있으십니다