백트래킹, Back Tracking

백트래킹

• 모든 경우의 수를 고려하는 알고리즘
• 모든 경우의 수를 탐색하면서, 더 이상 진행할 필요가 없는 후보는 탐색 X, 뒤로 돌아감
  • 진행할 필요가 없는 경우는 따지지 않으므로 브루트포스에 비해 시간 절약
  • 탐색 알고리즘으로, DFS, BFS로 모두 구현 가능.
• 재귀적으로 문제를 해결.

 

백트래킹 절차

1. DFS 수행 - 재귀를 통해 DFS 수행
2. 노드 검토 - 진행이 필요한 노드인지 검토 필요( 더 이상 진행할 필요가 없을 시 백트래킹 수행)
   1. 서브트리 이동 - 방문 노드위 하위로 이동(재귀를통해 DFS 수행)
   2. 백트래킹 수행 - 유효하지 않은 노드일 경우 상위노드로 이동(백트래킹 수행)

 

백트래킹 유망성 판단

백트래킹은 노드를 검토해 하위로 이동하거나, 백트래킹을 수행함.

이를 유망성이라고 함.

해가 될만한지 판단, 유망하다면 다음 노드로 이동, 유망하지 않다면 백트래킹 수행

해가 될 가능성이 있다면 유망하다(Promising)라고 하고, 유망하지 않아 노드로 이동하지 않는 것을 가지치기(Pruning)한다고 표현.

 

DP와 백트래킹의 차이점

DP

• 문제 해결에 있어서 Problem과 SubProblem을 찾는게 중요
  • 문제를 작게 쪼개어서 해결
  • Subproblem은 겹치면서(overwrapping) memolization 방법을 통해 문제를 해결함.

백트래킹

• Decision Space라 해서 우리가 가질 수 있는 모든 경우의 수를 하나씩 살펴 감.
  • 진행하면서 더 이상 진행할 필요가 없는 후보는 경우의 수를 따지지 않음.

---

대표 문제(N-Queen, 백준 9663번)

대표적인 백트래킹의 문제인 N-Queen 문제입니다.

NxN 크기의 매트릭스에 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 리턴하는 문제입니다.
알고리즘을 해결하는 흐름을 한번 알아보겠습니다.

N이 1, 2, 3, 4 …. 인 경우를 한번 생각해보자!

N이 1인 경우

- 1x1인 공간에 1개의 퀸만 넣으면 되므로 1개의 경우를 만족함.

 

N이 2인 경우

- 만족하는 경우 없음.

N이 3인 경우

- 만족하는 경우 없음.

N이 4인 경우

N이 4인 경우를 기준으로 한번 백트래킹 경우를 만들어 보겠음.

Dicision Space를 만드는 방법은 첫번 째 퀸의 위치를 다음과 같이 선택하면서 경우의 수를 만들어 나감

하나의 브랜치에서 총 16개의 노드가 생기는 것.

각각의 경우에서 또 16개씩 노드가 생기는데, 이때부터 이제 조건에 해당하는 브랜치만 살리고 나머지는 백트래킹 하는것이 중요함.

 

초록색 퀸의 위치를 보면 첫번째는 위치 중복, 두번째는 퀸의 공격 위치에 있으므로 조건 불만족이라 백트래킹하고, 3번째와 같이 유망한 위치에서 또다시 노드를 늘려 나가는 것임.

여기서 주의할 점은, 중복을 제거하는 것임.

만약 세번째 경우를 예로 든다면, 첫번 째 퀸이 초록색 위치이고, 노란색이 두번 째 퀸일 경우,

각각 다른 경우의 수지만 겹치는 것을 알 수 있음.

이를 해결하기 위해 전 단계 후보의 다음 위치에서만 선택할 수 있도록 하는 방법을 선택할 수 있음.

→ 중복 제거 가능시간

 

위와 같은 방법으로도 가능하지만, 시간이 너무 오래 걸림.

시간 절약을 위해 제한 조건을 다시 알아 보겠음.

1. 행이 겹치는 경우
2. 열이 겹치는 경우
3. 대각(좌, 우)이 겹치는 경우

여기서 행만 겹치는 경우를 생각해보자.

 

각 행에는 하나씩의 퀸 밖에 오지 못하므로,

Dicision Space가 기존의 16에서 4로 줄어든 것을 알 수 있음.

 

간단한게 알고리즘을 설계하는 흐름에 대해서 알아봤습니다.

생각을 실제로 구현하는 것도 어렵지만, 이런 흐름을 생각해내는게 진짜 어려운거 같아요..

알고리즘은 조금씩 공부하면서 느끼고 있습니다..

알고리즘 짱짱맨이 되는날까지 천천히 꾸준하게 해보겠습니다!!

---

코딩테스트, 기초, 백트래킹 backtracking 소개

[알고리즘] 백트래킹이란? (Swift) (feat.DFS/BFS)

[알고리즘] 백트래킹이란? (Swift) (feat.DFS/BFS)