현재 코드의 문제는 DP 배열을 효율적으로 사용하지 못하고 있다는 점입니다.
DP를 이용해서 시간복잡도를 줄이기 위해서는 같은 지점에 다시 방문했을 때, 추가적인 탐색 없이 DP의 값을 이용해서 바로 return할 수 있어야 합니다.
하지만 현재 dfs 함수에서 dp 배열을 사용하는 부분은 24줄(읽기), 32줄(쓰기) 뿐인데, 이전에 방문한 지점에 다시 방문했더라도 dp[current_row][current_col] > moveCnt 가 성립하면 DFS를 다시 시행하므로 탐색이 비효율적입니다.
이를 저격하는 테케도 만들 수 있습니다. 아래 테케의 정답은 66이지만, yongseong97 님의 코드는 몇 초가 지나도 정답이 나오지 않습니다.
(조금 복잡하게 생긴 테케지만, "1, 2, H"가 수없이 반복된 형태로, 한 지점에 방문하는 방법이 여러개입니다.)
따라서 이 문제를 해결하기 위해서는 이미 방문한 지점이라면 DP를 이용해 바로 최대 이동 횟수를 반환하도록 함수를 수정해야 합니다.
yongseong97 2년 전
안녕하세요 처음 dfs+dp를 이용해서 푼다는것 까지 알았습니다. 하지만 제 나름대로의 논리를 가지고 풀었으나 시간초과가 발생하였습니다.
이유와 반례를 알려주시면 감사합니다.
답답한 마음에 글을 올리는데 도움부탁드립니다.