gudrbscse   1년 전

BFS 로 구현 하였는데

틀렸다고 나오네요.

테스트 케이스 해봐도 정답으로 잘 나오는데

왜 그런지 모르겠네요..ㅠㅠ

한 수 배우고 싶네요 ㅠ

이미 방문한 점에 도달하는 더 짧은 경로를 발견하더라도 무시하는 코드로 보입니다.

trace[i][j]가 true/false가 아닌, 현재까지 찾은 시작점~(i,j)의 최단 경로의 길이를 저장하게끔 하고

이 값보다 작은 값으로 i,j를 다시 방문하게 되면 trace[i][j]를 갱신해주며 다시 그 점을 큐에 넣어주는 작업을 해주시면 맞을 듯합니다.

아 다른 문제인듯 싶네요 ㅋㅋㅋ 죄송합니다

move 함수 내부의 반복문이 큐가 빌 때까지가 아니라 Trace[n][m]이 false일 때까지만 돌아가도록 해보세요

gudrbscse   1년 전

감사합니다ㅎ

해결되었습니다.

empty 가 될 때 까지 보면 비 효율적이여서 틀렸다고 나왔던 것일까요?

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅠㅠ


N,M이 미로에서 가장 늦게 방문된다는 보장이 없기 때문입니다. 예를 들어

4 7

1111111

0000001

0000001

1111111

과 같은 미로에서, N,M에는 10칸만에 방문에 성공하지만 큐가 비지 않았기 때문에 N,1에 16칸만에 방문할 때까지 계속 돌게 되고 count가 최종 16이 되어버려요

댓글을 작성하려면 로그인해야 합니다.