mhccc   5년 전

강의자료 참고해서 코드 구현했습니다. dfs 변형과 메모이제이션을 활용하는 방법입니다.

왜 dp배열의 초기값을 -1로 해주어야 시간초과가 나지 않는 것인지 궁금합니다.

질문들을 검색해보니 dp[x][y]가 0일 때, 경로가 없어서 0인지, 처음 방문이라 0인지 구별이 안되어 시간 초과가 나는 것이라고 합니다.

제 코드에서는 1, 1 지점에서 재귀 호출을 시작합니다. 내리막길 경로가 더 이상 존재하지 않으면 return 되어 이전 함수 호출로 돌아오게 되고 결국 go(1, 1) 함수 호출 시점으로 돌아오게 되어 dp배열을 -1로 초기화 하지 않아도 무한 호출이 일어나지 않을 것으로 예상되는데 제가 무엇을 잘못생각하고 있나요??

도움 부탁드립니다. 감사합니다.

djm03178   5년 전

이 경우 시간 초과가 나는 것은 무한 재귀 호출 때문이 아니라, 시간복잡도가 지수이기 때문에 그렇습니다.

방문한 것과 안 한 것을 구분하지 못한다는 건 곧 완전탐색과 같고, 이는 재귀 깊이가 깊어질수록 상상을 초월하는 속도로 호출 횟수가 늘어나게 됨을 의미합니다.

보다 간단한 예로, https://www.acmicpc.net/proble... 이 문제에 쓰여있는 코드를 그대로 실행했을 때, n을 조금만 키워도 0과 1이 얼마나 많이 출력되는지 확인해볼 수 있습니다.

재귀 호출 과정을 트리 형태로 그려보시면 쉽게 이해할 수 있습니다.

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