인프런 커뮤니티 질문&답변

안녕하세요 준혁님ㅎㅎ

            visited[ny][nx] = 1;
            q.push({ny,nx});
            answer++;       // 한번 이동할 때마다 증가

이렇게 answer에 담아서 풀이를 하셨는데 이렇게 하시면 안됩니다.

bfs는 최단거리 배열을 이용해서 푸는 문제고 그걸 잘 활용해야 하는데요.

이런식으로 구축해야 합니다.

            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny,nx}); 

왜 그러면 준혁님 코드는 안될까요?

저 부분은 다음과 같이 구동이 됩니다.

왼쪽 노드에서 오른쪽 노드들로 이동한다고 했을 때 분명 최단거리는 2가 찍혀야 하는데 ans는 다음 노드를 탐색할 때마다 ++가 되며 결국 3이 찍히게 되거든요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.