legendmic2   1달 전

DFS로는 계속 시간초과가 나서, BFS로 다시 풀고있습니다.

그러던 중에, 왜 시간초과가 나는지 궁금해서 질문드립니다.

질문게시판에서 알려주신 반례중 가장 대표적인 것이 {1, 0}이었는데요, 제 코드도 이때 오류가 납니다.

디버깅을 해보니, pos==4700일때 stack overflow라는 exception이 뜨더라구요.

컴파일러에 할당된 메모리보다 더 많은 연산처리를 필요로해서 멈춰버리는건가요?

끝까지 읽어주셔서 감사합니다.

tofhddl9   1달 전

현재 visited 배열을 사용하지 않고 계시는데 그래서 DFS 함수 호출이 엄청 많이 될거에요.

그리고 DFS는 방문순서가 최단 거리를 보장하지 않기 때문에 단순히 방문여부를 체크하는 visited 배열 보다는 거리에 대한 배열이 필요할듯 합니다.

sonjaewon   1달 전

이 문제 같은 경우는 깊이가 무한이기 때문에 dfs 하면 무한 루프 빠집니다.

너비 우선 탐색을 써보세요

legendmic2   19일 전

@tofhddl9

@sonjaewon

감사합니다ㅠㅠ!

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