ohsemin4   3년 전

결국 dfs, dp배열로 이용하여 풀긴 풀었지만 이전에 푼 코드가 왜 시간초과가 나는지 정확히 이해할 수 없어서 이렇게 질문을 남기게 되었습니다.

먼저 제가 푼 방식은 마지막 도착지점으로부터 출발지로 되돌아가는 방식을 사용하여 dfs + dp + 백트래킹 이 3가지 방법을 이용하여서 풀었습니다.

dp배열에는 현재 도착지점에서 그 지점까지 가기 위한 코스트를 저장하였습니다. 그리고 다음에 dfs 탐색시 만약 이미 dp 배열에 저장된 값보다 더 큰 값이 아니라면 탐색을 하지 않도록 진행하였습니다.

어떤 부분에서 시간이 많이 걸리거나 overlap 되는지 전혀 모르겠습니다.

결국 dp배열에 저장되는 값을 다르게 하여 풀긴하였지만 이 코드가 왜 시간 초과인지 정확히 모르겠어서 이렇게 질문 남겨 봅니다.

고수분들의 도움 부탁드립니다. 부탁드립니다... 

코드에 약간의 수정을 진행하였습니다.

윗부분은 자바이며 주석 밑부분은 c++입니다.

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