js0304   1년 전

그래프에서 1을 찾을 때마다 bfs를 돌려 graph를 업데이트하고, 최종적으로 가장 거리가 먼 값을 출력하는 방식을 사용했는데 메모리 초과가 떴습니다.

다시 공부하여 1의 좌표를 모두 q에 넣고 시작하니 해결이 되더군요.

첫 방법은 왜 메모리가 터지고, 정답 코드는 왜 안 터졌는지가 궁금합니다.

조언 부탁드립니다!

oh040411   1년 전

두 번째 bfs부터는 graph[nx][ny] >= cnt+1 를 만족하면 큐에 들어가게 되는데, 이때 방문 처리를 별도로 하지 않으면 큐에 중복된 좌표가 계속 들어가게 되어서 메모리 초과가 납니다. 자세한 내용은 https://djm03178.tistory.com/3... 이 글을 참고해보세요. 이 문제를 해결했더라도 bfs가 최대 100만번 수행되므로 시간 초과를 받을 것입니다.

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