twinshj0604   1년 전

예제는 다 나오는데 2%에서 메모리 초과로 계속 터지는데 이유가 뭔가요?

js0304   1년 전

안녕하세요, 저도 메모리 초과로 꼬박 3일을 고민하고 깨우친 부분 공유드립니다.

bfs를 수행할 때, 기본적으로 visit 처리는 queue에 append 해주는 타이밍과 동시에 이루어져야 합니다.

그렇지 않으면 queue에 중복된 좌표들이 많이 겹쳐, 이 문제처럼 범위가 커질 때 메모리가 터지게 됩니다.

백준 1260번 문제의 예제 1과 같은 case를 보시면, append 할 때 visit처리를 하지 않고 pop할 때 처리를 하면, queue에 같은 노드가 중복되어 들어가게 됩니다. 다만 해당 문제의 dfs를 풀이할 때는 제시된 그래프의 형식과 의도에 맞게 visit처리를 pop 할 때 수행하도록 합니다. dfs를 재귀로 구현하는 경우가 많은 이유기도 한 듯 합니다.

따라서 이 부분을 고려할 때, visit 처리의 타이밍에 대해 고민해보시면 좋을 것 같습니다.

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