Back Tracking
Back Tracking이란 현재 상황에서 선택 가능한 경우의 수를 하나씩 모두 살펴보며 탐색하는 알고리즘이다.
위의 그림이 스도쿠를 backtracking을 사용하여 푸는 과정을 나타낸 것인데, 일단 가능한 수에 대해서 선택을 거듭하다가 각 흐름의 실패/성공의 결과를 전달해 판별한다.
쉽게 생각하면 우리가 평소에 많이 하는 게임을 예로 들 수 있는데, 수많은 선택지에 따라 스토리가 다른 방향으로 전개되는 것 처럼 각각의 선택지를 타고 들어가서 최종결과를 본 뒤, 그 결과를 Back tracking 하여 알려준다고 생각하면 될 것 같다.
아무래도 선택지에 따른 하위 항목들이 계속해서 생겨나는 만큼, 그 흐름을 Tree구조로 잘 구현하는게 중요할 것 같다.
또한 Back tracking은 선택지를 따라 들어가다 끝에서 처음으로 올라가 결과를 알려준다는 점에서 재귀 함수와도 연관이 있다.
백준 예제 N과M 시리즈 를 풀어보면 감을 잡는데 많은 도움이 될 것이다. 백준 N과M모음
예제1 ) N과M (1)
문제링크 이 문제는 1-N까지의 자연수 에서 중복없이 M개를 고른 수열을 만드는 문제다.(순열)
python의 경우 itertools 안에 permutations라는 함수가 이미 구현이 되어있지만 이걸 쓰면 의미가 없기에 재귀 함수를 사용해 직접 구현.
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
arr = [i+1 for i in range(n)] #1-n list
check = list() #중복 출력을 피하기 위한 리스트
def func(c):
if c==m: #최대깊이
for num in range(n):
if num+1 not in check:
for base in check:
print(base,end=' ')
print(num+1)
return
if c<m: #최대깊이까지 재귀호출
for num in range(n):
if num+1 not in check:
check.append(num+1)
func(c+1)
del check[c-1:m-1] #현재 단계부터 저장된 check안의 수 삭제
func(1)번외) permutations함수를 사용하여 푼 코드
import sys
import itertools
input = sys.stdin.readline
n,m = map(int,input().split())
arr = [i+1 for i in range(n)]
p_arr = itertools.permutations(arr,m)
for each in list(p_arr):
print(' '.join(map(str,each)))예제2) N-Queen
마찬가지로 back tracking(재귀)를 이용하여 푸는 문제다. 문제링크
N=15의 그렇게 크지 않은 숫자임에도 불구하고, Time complexity가 워낙 큰 탓에 python으로 제출할 시 시간초과가 뜬다..(10이상부터 급격히 느려짐)
import sys
input = sys.stdin.readline
n = int(input())
arr = [([0]*n) for _ in range(n)]
exist = list()
result = list()
def func(y):
if y == n:
result.append(1)
return
for x in range(n):
if check(x,y) is False:
continue
exist.append([x,y])
func(y+1)
del exist[-1]
def check(x,y):
possible = True
for each in exist:
if abs(each[0]-x) == abs(each[1]-y): #cross position
possible=False
return False
if each[0]==x or each[1]==y:
possible=False
return False
return possible
func(0)
print(len(result))