[Algorithm04] 백트래킹
전 시간인 완전탐색의 기본에 대해서 공부했다. 오늘의 백트래킹에 대해 공부하기 전에 짧게 복습하면 완전탐색은 근본적으로 반복문과 조건문을 활용하여 문제에서 주어진 조건에 부합하는 가능한 모든 경우의 수를 탐색하는 것이다. 오늘 공부할 백트래킹은 완전탐색 중(우리는 dfs기본을 이용하여 완전탐색을 진행했다) 문제에서 주어진 조건을 활용하여 경우의 수를 끝까지 탐색하기 전에 미리 체킹 하여 불필요한 탐색 시간을 줄이는 방법이다.
그럼 어떻게 불필요한 탐색 시간을 줄일 수 있는지 알아보자
백트래킹
백트래킹이란 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다.
여기서 지금의 경로가 해가 될 거 같지 않으면을 체크하는것을 유망조건을 확인한다라고 한다.
재귀를 돌면서 즉 완전 탐색을 하는 도중 다음 재귀를 넘어가기 전에 다음을 확인할 필요가 있을지를 확인하는 유망조건 판단 후에 넘어갈 필요가 없으면 더 탐색하지 않고 이전 단계로 돌아간다.
나머지는 일반적인 dfs와 동일하지만 유망조건을 체크하는것으로서 즉 얼마나 가지치기를 잘함으로써 시간을 더 줄일 수 있는가로 나뉜다. 하지만 시간복잡도로서 여전히 최악의 경우 N! 의 복잡도를 가지기 때문에 n의 크기가 말도 안되게 큰 문제에서는 사용이 힘들다.
말이 이래저래 길지만, 사실 우리는 백트래킹을 이미 사용하고 있다. 순열과 조합에서부터 전 시간에 진행한 완전탐색 문제 풀이 중에서도 백트래킹이라는 기법을 사용하고 있었다.
조합을 생각해보자 모든 경우의 수중에서 k개만 뽑지 않는가! 주어진 n개에서 나올 수 있는 모든 조합에 대해서 k개만 뽑는 다라 좀 더 생각해 보면 모든 조합을 탐색하는 도중 탐색한 조합의 수가 k개가 넘어가면 더 탐색하지 않고 돌아간다.(if depth==k:)로 말이다. 사실 이러한 백트래킹은 우리가 문제를 풀면서 무조건 필요하다. 어떠한 조건에 부합하는 답을 찾아야하니 말이다.
다음은 기본적인 백트래킹 구조이다. 외울 필요없다 조건을 처리해야 하는 부분은 어차피 우리가 문제에서 주어진 조건을 구현하는 능력이 필요하니 그 조건을 잘 설정하는 능력을 길러야 한다.
def backtracking(x):
if 정답:
출력/저장
else:
for 자식노드:
if 자식노드가 유망한지(promising): 유망하면
자식노드로 이동
backtracking(x+1)
부모노드로 이동
기본적인 완전탐색(dfs 기본) 코드와 비슷하다!! 자식노드가 유망한 지 체킹 하는 promising 부분을 보면 이 부분도 어디에서 많이 봤다!
자 복습시간이다 4장의 카드에서 3장의 카드를 뽑는데 중복을 허용하지 않고 순서를 고려한다고 생각해 보자
중복 없이 뽑아야 하기 때문에 visited로 사용 유무를 체킹 하여 다음 카드를 뽑으러 갈지 말지 판단한다.
아래 코드를 보면 기가 막히게 비슷한 것을 볼 수 있다.
# 순열
# 중복 허용 x, 순서가 다르면 다른 경우의 수
# 4장의 카드 중에서 3장 뽑기
card = ['A', 'B', 'C', 'D']
path = [0] * 3
# visited 배열 사용하여 카드 중복 사용 유무 확인
visited = [0] * 4
def dfs(depth):
# 3장 모두 뽑았으면 출력하고 return
if depth == 3:
print(*path)
return
# 카드 4장 확인하기
for i in range(4):
if visited[i] == 0: # 아직 사용하지 않은 카드이면
visited[i] = 1 # 사용 체크 하고
path[depth] = card[i] # 카드 뽑기
dfs(depth + 1) # 다음 카드 뽑으러 가기
visited[i] = 0 # 리턴 이후에는 다시 사용 체크 해제
path[depth] = 0 # 뽑은 카드 초기화
dfs(0)
이렇게 백트래킹은 뭔가 대단한 것이 아니라 단순히 탐색을 하는데 다음 노드로 넘어가기 전에 조건을 먼저 체킹 하여 다음 노드를 더 확인할지 말지를 확인하는 것이다. 이것의 꽃은 N-queen 문제이다.
실제 문제를 보며 우리가 배운 방법들을 적용시켜 보자
우리는 앞전부터 탐색문제에서의 기본은 순열과 조합이고 그것을 재귀를 활용하여 풀었다. 이 문제에서 요구하는 것은 무엇인가 한번 확인해 보자
<N x N의 개의 체스판에서 N개의 퀸을 놓는다> 즉, NXN개에서 N개를 뽑는다. 그리고 추가적 조건을 생각해 보자 서로 공격할 수 없게 퀸을 놓는 거니 퀸과 퀸끼리 만날 때는 같은 행과 열 그리고 대각선에는 퀸을 뽑으면 안 된다.
자 그럼 기본적으로 NXN개에서 N개를 뽑는데, 첫 번째 퀸을 뽑고 두 번째 퀸을 뽑을 때 그다음에 올 퀸의 자리가 같은 행, 열 그리고 대각선에 있는지를 미리 확인해서 재귀를 돌지 말지 결정한다. 이것이 바로 유망조건이다. 다음에 올 퀸의 자리가 만약 서로 공격할 수 있는 자리라면 어차피 그다음 퀸을 뽑든 안 뽑든 이미 조건에 위배되는 조합이기 때문에 그 이후로는 더 확인할 필요가 없다.
해당 코드에서는 코드의 가독성을 위해 유망조건을 따로 함수화 시켜서 만들었다.
def is_promising(col, i, j): #유망한지 확인하는 메소드
for k in range(1, i):
if col[k] == j or abs(col[k] - j) == abs(i - k): #같은 행이 아니고 대각선에 있을경우 false 더 이상 밑으로 트래킹 하지 않음
return False
return True
def queen(i, col, count): #i는 깊이 col은 배열 count는 정답트래킹 횟수
n = len(col) - 1 # 0부터 시작하기 때문에 배열 길이의 -1
if i > n: # 종료 조건 깊이 가변 변수 i가 아직 깊이 n(배열의 길이)보다 길어지는 순간
return count + 1 #횟수 증가
else:
for j in range(1, n + 1):
if is_promising(col, i, j): # 유망 조건 체킹
col[i] = j
count = queen(i + 1, col, count)
return count
n = int(input())
col = [0] * (n + 1)
print(queen(1, col, 0))여기서 중요 포인트는 기본적인 dfs의 틀을 지키고 거기에 백트래킹 조건 즉 유망조건을 어떻게 설정하느냐가 관건이다.
코드에 대한 자세한 풀이는 하지 않을 것이다. 나와 똑같이 풀지 말고 반복문의 시작과 끝을 어떻게 정하고 종료조건을 어떻게 정하고는 다 다르게 할 수 있다. 이러한 자세한 부분들은 직접 하나하나 디버깅해보면서 느껴야 나중에 혼자 풀 수 있다.
사실 탐색문제는 진짜 쉬운 문제가 아닌 이상 이렇게 조건을 주고 조건에 부합하는 경우의 수를 탐색하는 문제가 나온다.
우리는 많은 문제를 연습해 보며 탐색문제를 푸는 나만의 방법을 만들고 조건을 구현하는 연습을 해야 한다.
dfs의 틀은 당연히 바로 나와야 하고 유망조건을 만드는 구현실력을 길러야 문제를 맞히는 키가 될 것이다.