[Algorithm] 백트래킹(Backtracking)

 

BOJ 1987번 알파벳 문제를 단순히 DFS로 풀다가, dx, dy로 나아가는 방향 선정에 따라 답이 달라지는 것을 느껴

 

관련 알고리즘인 백트래킹에 대해 정리하려고 한다! 

 

백트래킹(Backtracking) 알고리즘의 정의

 

  -  ' 가능한 모든 방법을 탐색한다 ' 라는 아이디어를 가진 알고리즘

 

  -  백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며, 해결책에 대한 후보를 구축해 나아가다, 

 

가능성이 없다고 판단되는 즉시 후보를 포기하면서 정답을 찾아가는 알고리즘이다. 

 

  -  즉,  해를 찾는 도중 해가 아니어서 막히게 되는 경우 ->  '다시 되돌아가서' 해를 찾아가는 기법

 

  -  최적화 문제와 결정 문제를 푸는 방법

 

 

DFS와 백트래킹

 

  1.  깊이 우선 탐색(DFS)

 

    -  DFS는 가능한 모든 경로(후보)를 탐색하는 알고리즘으로,

 

       현재 지점에서 방문할 곳이 있는 경우 재귀 호출을 이용해 반복해서 이동한다.

 

  ->  불필요할 것 같은 경로의 사전 차단과 같은 경우의 수를 줄이는 행위 불가

 

    -  N! 가지의 경우의 수를 가진 문제는 DFS로 처리 불가

 

    -  따라서, 이러한 DFS의 비효율적인 경로를 차단하고, 목표지점에 도달할 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘

 

 

  2.  백트래킹(Backtracking)

 

    (1)  가지치기(Purning) 을 통해 효율 극대화

 

      1)  가지치기 : 가능성이 없는 루트를 가지치키로 쳐내서 탐색하는 기법

 

      2)  해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않은 경우

 

     ->  그 경로를 더 이상 가지 않고 되돌아감

 

     ->  반복문의 횟수를 줄여 효율성 향상

 

      3)  가지치기 방식에 따른 효율성 결정

 

        -  일반적으로, 불필요한 경로의 조기 차단으로 경우의 수를 줄일 수 있지만,

 

        -  N! 과 같은 경우의 수를 가진 문제에서 최악의 경우에는, 여전히 지수함수 시간을 필요로 해 처리 불가능할 수 있음

 

        -  따라서, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정됨

 

 

백트래킹 기법의 유망성 판단

 

  -  어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후

 

-> 유망하지 않다고 결정되면 -> 그 노드의 이전(부모)로 돌아가(Backtracing) -> 다음 자식 노드로 이동

 

  -  해가 될 가능성이 있으면 -> 유망하다(promising)고 하며, 

 

  -  유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것

 

 

풀어 볼 문제

 

  -  BOJ 15649번 : N과 M(1)

 

  -  BOJ 9663번 : N-Queen

 

 

 

참고

  -  https://velog.io/@mmindoong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking

  -  https://chanhuiseok.github.io/posts/algo-23/