1963 소수 경로를 풀면서 dfs와 bfs의 차이를 절실하게 느낄 수 있었다.

문제는 인풋으로 start소수 end소수를 받는다. start소수의 한자리씩만 바꿀 수 있으며 바꾼 후에도 소수여야만 한다. 그래서 end소수를 만들 때 까지 걸리는 최소 횟수를 출력하는 문제이다.

처음에 접근한 방법은 dfs였다. 나는 bfs가 귀찮아서 보통 dfs로 문제를 풀곤 했다. 사실 차이점을 잘 느끼지 못했다.

한자리를 기준으로 잡아서 전역배열로 방문체크를 하고 dfs를 하는 방식으로 생각했다. 결국 end소수까지 찾아갈 수는 있었다. 하지만 문제는 쓸데없이 매우 깊다는 점이었다. 6번이면 찾을 end소수를 800 깊이까지 들어가서야 찾을 수 있었다. 처음에 접근할 때는 dfs를 하다보면 최솟값으로 갱신될 줄 알았지만 이는 오산이었다.

깊이 우선으로 들어가다 보니 첫 dfs에서 방문체크가 다되었고 그 다음 dfs는 방문체크가 다 되었으므로 탐색을 하지 않고 마친다.

방문체크를 어떻게 해야하나 머리를 굴렸지만 해답을 찾을 수 없었다.

잠깐 쉬고 보니 답은 간단했다. bfs를 쓰면 된다. bfs는 너비우선 탐색이기 때문에 start소수에서 갈 수 있는 소수만 큐에 push하고 큐에 있는 data를 pop하면서 end소수와 같은지 비교하면 된다. 만약 같다면 큐의 breath(너비)가 최소횟수가 되고 return;으로 함수를 종료시킨다. 만약 큐가 빈다면 end소수로 가는 경로가 없으므로 impossible을 출력하고 종료한다.

-----------------------------------------

위의 글이 제가 문제를 풀면서 느낀 의식의 흐름입니다. 혹시 dfs로 푸신 고수분 계신가용...
고수님들의 의견이 궁금합니다..

제 코드는 공개되어있습니다.