Backtracking 1 썸네일형 리스트형 BackTracking Design Pattern에 대하여 BackTracking이란 Tree search 중에 DFS[depth first search]에서 파생한 디자인 패턴이다. 기본적으로 DFS를 실시하고 탐사 중에 Dead-End에 도달하면, 즉 더 깊은 depth에서 해답을 찾을 수 없다고 판단하게 되면 아직 탐사하지 않은 노드를 자식 노드로 가지고 있는 노드를 찾을 때까지 이전 탐사의 경로를 되짚어 간다. 그리고 이 것을 BackTracking 이라고 한다. 이 알고리즘 디자인 패턴에서 많이 언급되는 것이 N-Queens problem이다. 문제를 보면서 생각해보자. N-Queens problem이란 N∗N 크기의 체스판에 서로 공격이 불가능한 N개의 퀸을 배치할 수 있는 경우의 수를 구하는 문제이다. 먼저 a8에 퀸을 배치한 상황을 고려해보자... 이전 1 다음
