boffin   2년 전

잘 돌아가는데 제출해보면 런타임에러가 뜨네요

왜 그럴까요..?ㅠ

djm03178   2년 전

che에 값을 나중에 대입해서 그렇습니다. 가령, 2x2 맵의 모든 칸이 이동할 수 있는 칸이면 che가

0 0

0 0

과 같은 상태에서 출발하고, 한 번 루프를 돌면

1 0

0 0

이 되어 있을 것이고, 그 다음은

1 1

0 0

이 될텐데, 이 때 이미 (2, 2) 좌표는 큐에 들어간 상황입니다. 그러나, 그 다음 루프에서는 (2, 1) 좌표를 검사하게 되고, 여전히 che[2][2]는 0이기 때문에 (2, 2)가 큐에 또 추가됩니다. 즉, 같은 좌표를 중복해서 방문하는 일이 발생합니다.

좌표의 수가 최대 10000개이고 큐의 크기도 10001인데, 큐에 중복해서 들어가는 좌표가 여럿 생기면 결국은 큐의 크기를 초과하게 될 수 있습니다. 그래서 BFS를 할 때는, 큐에 추가하는 순간에 그 좌표의 방문을 먼저 기록해두는 것이 좋습니다.

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