effort0819   2년 전

dfs 백트래킹을 사용할경우 시간복잡도를 계산해서 시간초과가 날지 안날지 어떻게 알 수 있을까요?

최대 20 by 20 이니까 400.. 방향이 4개... 4^400.. 그러나 가지않는방향, 지나왔던 것을 체크하는데.. 복잡도를 구해서 시간초과날지 미리 알 수 있을가요?

portableangel   2년 전

알파벳은 서로 다른 26개이기 때문에, 경로는 길어야 26의 길이를 가집니다. 따라서, 많아야 4^25만큼 연산하게 됩니다.

또한, 방금 왔던 방향으로는 이미 지나친 알파벳이 써 있어서 못 가기 때문에, 각 칸에서 선택할 수 있는 다음 방향은 (첫 칸을 제외하면) 항상 3칸 이하입니다.

따라서 연산량은 3^25 정도로 줄어듭니다.

만약 경로가 중간에 인접하게 된다면 3개보다 적은 방향을 가지게 됩니다.

또한, 가장자리나 변에서는 이동할 수 있는 칸이 더 줄어들게 됩니다.

사실 그래도 시간 내에 들어갈지 아직 확신할 수는 없지만.. 연산량이 많이 줄었음을 볼 수는 있지 않을까요?

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