yongseong97   2년 전

안녕하세요 처음 dfs+dp를 이용해서 푼다는것 까지 알았습니다. 하지만 제 나름대로의 논리를 가지고 풀었으나 시간초과가 발생하였습니다. 

이유와 반례를 알려주시면 감사합니다.

답답한 마음에 글을 올리는데 도움부탁드립니다. 

powergee   2년 전

현재 코드의 문제는 DP 배열을 효율적으로 사용하지 못하고 있다는 점입니다.


DP를 이용해서 시간복잡도를 줄이기 위해서는 같은 지점에 다시 방문했을 때, 추가적인 탐색 없이 DP의 값을 이용해서 바로 return할 수 있어야 합니다.

하지만 현재 dfs 함수에서 dp 배열을 사용하는 부분은 24줄(읽기), 32줄(쓰기) 뿐인데, 이전에 방문한 지점에 다시 방문했더라도 dp[current_row][current_col] > moveCnt 가 성립하면 DFS를 다시 시행하므로 탐색이 비효율적입니다.


이를 저격하는 테케도 만들 수 있습니다.  아래 테케의 정답은 66이지만, yongseong97 님의 코드는 몇 초가 지나도 정답이 나오지 않습니다.

(조금 복잡하게 생긴 테케지만, "1, 2, H"가 수없이 반복된 형태로, 한 지점에 방문하는 방법이 여러개입니다.)

따라서 이 문제를 해결하기 위해서는 이미 방문한 지점이라면 DP를 이용해 바로 최대 이동 횟수를 반환하도록 함수를 수정해야 합니다.

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