질문있습니다.

Question

선생님 방문한 map 을 1로 바꾸시는데 int dx[] ={1, 0, -1, 0} int dy[] ={0, 1, 0, -1} 0 0 1  0 0 1 1 0 0 이 경우 (1,1)에서 (1,2),(2,1)을 차례로 방문후 1 1 1 1 0 1 1 0 0  이 상태에서 (1,2)에서 다시 for문 돌면서 (2,2)를 1로 변경합니다. 1 1 1  1 1 1  1 0 0  그럼 큐에 남아있는 (2,1)에서 (2,2)로 가는 경우가 사라지게 되는데 이 경우 무시해도 괜찮나요? 최단거리값이라 상관없는건가요?  큐에서 pop()해서 직접 방문한것도 아니고, 큐에push()만 했는데 방문한걸로 취급(?)해도 되나해서요 질문이 엉뚱하죠 뭔가 찜찜?해서 질문드려요ㅋㅋ 강의 잘 보고 있습니다. 좋은하루되세요

김태원 · Answer

감사합니다^^ 큐를 이용한 BFS 탐색은 출발점에서 한 번 만에 갈 수 있는 곳을  큐에 다 넣고 그 다음 두 번만에 갈 수 있는 곳을 다 넣고... 이런식으로 레벨탐색을 합니다. 즉 큐에서 먼저 나온 것이 가장 최단입니다. 나중에 나온것이 같은 지점으로 갈 수 있지만 앞에 나온 것보다 거리가 같거나 아니면 더 큽니다. 그래서 나중에 나온것은 무시해도 됩니다.