[ Algorithm ] 백트래킹 알고리즘

백트래킹 (Back-Tracking)

백트래킹은 해를 찾는 도중 해가 아닌 경우 다시 되돌아가 다시 해를 탐색하는 알고리즘이다.

일반적으로 그래프나 트리의 모든 원소를 완전탐색하기 위해서 많이 사용된다.

백트래킹은 재귀함수를 이용해 구현할 수 있다. 정석적인 완전 탐색과는 다르게 조건에 따라서

더 유망한 노드로 이동한다.

 

백트래킹 알고리즘을 이용하여 풀 수 있는 문제

백트래킹을 이용한 코딩테스트 문제중에서 가장 유명한 N퀸 문제이다.

탐색을 진행하면서 유망한 경우에 대해서만 탐색을 진행해야 한다.

예를 들면 미리 table을 만들어두고 탐색을 진행한 후 문제의 조건대로 경로가 겹쳐

탐색할 필요가 없는 table의 index번째를 false에서 true로 바꾸어 미리 건너뛰어 줄 index를

지정한 후 재귀탐색을 하는 방식으로 풀이할 수 있다.

 

백준 코딩테스트 페이지: https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

마치며...

공부하면서 이해하기 가장 어려웠던 방식의 알고리즘이었다. 특히 재귀적으로 처리한다는 방식 자체가 처음 접했을때 상당히 혼란스러웠다. 이해하기 어려운 만큼 하나씩 직접 그림을 그리면서 적용해보면서 이해할 필요가 있었다. 초반에 로직에 대한 이해 때문에 내가 애용하는 Google Keep에 하나씩 적으며 풀이해둔 것을 저장해 두었다. 혹시 시간이 지나고 재귀적인 처리작업을 불가피하게 해야 할 때 포스팅과 Google Keep을 다시 보며 복습해야겠다...