thirdcow   3년 전

1. 좌표의 상태를 유지하기 위해 매 방문마다 배열을 만들고 복사하는 작업은 비용이 너무크다.

2. 1에 대한 대안으로 벽을 이미 부순 경우, 아직 부수지 않은 경우 두 가지만 전역에 배열을 선언한다.

3. 이 방법으로 dfs를 수행할 때 순환을 막기 위해서 지나온 배열은 다시 못지나가게 체크한다.

4. 다만, 현재 택한 길이 최적의 길이 아닐 수 있으므로 dfs수행이 종료된 시점에서 못지나가게 체크한 부분을 원상복구한다.

5. dfs는 깊이를 우선으로 탐색하기 때문에(최적이 나와도 최적인지 모르기 때문에) 전부 탐색해야 한다. => 시간초과

6. 백트래킹을 이용해 시간을 줄여볼 수 있지만 여전히 최악의 경우를 배제할 수 없다.

daezang102   1년 전

일부러 dfs로 풀어보았는데 시간초과가 가장 큰 이유인것 같아요! 감사합니다

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