[Python] 백트래킹(Backtracking)

Saemi Min·2023년 1월 31일
0
post-thumbnail

백트래킹(Backtracking)

개념

= 퇴각 검색

  • 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
  • 최적화 문제와 결정 문제를 푸는 방법

DFS(깊이 우선 탐색) vs Backtracking(백트래킹)

  • DFS
    : 가능한 모든 경로(후보)를 탐색한다.
    : 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.
    : N!가지의 경우의 수를 가진 문제는 DFS로 처리 불가능!

- Backtracking(백트래킹)
: 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.
: 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.
=> 특정한 조건을 만족하는 경우만 살펴보는 것

  • 가지치기(Pruning) : 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미
    : 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.
    => 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것

코드

ex) 홀짝 만들기

A, B, C 세 사람이 가지고 있는 숫자를 차례대로 하나씩 줄 세운다.
단, 조건은 짝수나 홀수가 연속으로 2번 나오면 안된다.
이때 만들 수 있는 숫자를 모두 구하라.
(순서는 A-B-C)

  • A=1 / B=4 / C=7 -> 가능
  • A=1 / B=4 / C=8 -> 불가능
  • A=1 / B=4 / C=9 -> 가능
  • A=1 / B=5 -> 불가능 (바로 B의 다음 숫자로 넘어감)
  • A=1 / B=6 / C=7 -> 가능
    ...
    이런식으로 조건을 하나씩 대입해가면서 만약 조건에 맞지 않는다면 그 즉시 중단하고 다음 숫자로 넘어감
    그리고 모든 경우를 탐색해 가능한 모든 숫자 조합을 찾아냄

백트래킹 사용하는 문제

백준 9663 : N-Queen 문제 문제 링크
백준 15649 : N과 M 문제 문제 링크

profile
I believe in myself.

0개의 댓글