백트래킹(Backtracking) 활용 예

미로 내의 출발지(2)에서 시작하여 도착지(3)에 도달할 수 있는가 여부를 반환하는 문제를 통해 백트래킹의 개념을 간단히 확인 [요약] 백트래킹은 해를 찾는 과정에서, 현재 임시로 구한 해가 최종해에 도달 가능한가를 검사한다. 이를 통해 확인이 불필요한 경우의 수를 제외해가며 최종해를 찾는다. 백트래킹 [백트래킹과 깊이우선탐색(DFS)] 백트래킹은 DFS와 자주 비교된다. 이번 길찾기 문제를 이용해 비교하자면, DFS를 이용하면 경우 출발지와 이어진 모든 길을 탐색하고 그중 도착지와 연결된 곳이 있는지 확인할 수 있다. 백트래킹을 이용하면 출발지와 연결된 길이 얼마나 있든, 또 그중에서 도착지로 연결된 길이 몇 개든 상관없이, 출발지와 도착지를 연결하는 경로를 하나라도 찾으면 해가 존재 함을 반환한다. 예를 들어 만일 출발지에서 도착지로 가는 최단 경로를 찾는경우 백트래킹이 아닌 모든 경로를 확인가능한 DFS이용하는 것이 적절하다. [문제] 아래와 같이 0,1,2,3의 숫자로 구성된...

원문링크 : 백트래킹(Backtracking) 활용 예