미로 탐색
-
미로 탐색Algorithm with C/BackTracking 2020. 8. 26. 19:26
0. 참고 문헌 1. 개념 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데, 이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다. 여기에서 부분 문제의 답은 어느 것이라도 될 수 있다. 선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로. 게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고, 그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다. 백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있..