그래프 이론 - 2. 백트래킹 (Backtracking)

정의

백트래킹이란 문제의 해가 될 수 있는 후보들을 탐색하면서, 각 후보들이 해가 될 가능성이 없다고 판단될 시 해당 후보를 버리는 방식이다.

 

예시

백트래킹을 활용할 수 있는 대표적인 유형의 문제로 스도쿠가 있다.

 

출처: https://en.wikipedia.org/wiki/Backtracking

 

스도쿠의 칸이 충분히 많이 채워져 있다면 논리적 추론 만으로 풀 수 있지만, 그렇지 않다면 어느 정도 무작위 대입이 필요하다. 이 문제를 브루트 포스 방식으로 푼 다면, 고려해야 할 경우의 수는 9^n 으로 매우 크다.

 

효율성 향상을 위해서는, 현재 단계에서 규칙을 만족하지 못할 시, 더 진행하지 않고 이전 단계로 돌아가 현재 사용한 값대신 다음 값을 대입하는 방법을 써야 한다.

 

 

 

백준에 있는 스도쿠 문제를 예시로 들겠다.

 

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

예제 케이스의 빈칸은 51개이다. 가능한 모든 경우의 수인 9^51를 전부 확인하는 것은 매우 비효율적일 것 이다.

만약 특정 칸이 스도쿠의 제약 조건을 만족하지 못한다면, 나머지 칸들을 탐색하는 것은 의미가 없는 일이다. 따라서, 제약조건을 만족하지 못하는 칸이 나온다면 해당 칸을 고정한 상태로 다음 숫자를 탐색하는 것이 아니라, 더 진행하지 않고 제약 조건을 만족하지 못한 칸에 다음 숫자를 대입 하는 것이 더 효율적이다.

 

위 스도쿠 문제를 백트래킹을 이용하여 해를 찾는 파이썬 코드는 다음과 같다.

 

# 입력
a=[[*map(int,list(input().rstrip()))] for _ in range(9)]

# 빈칸의 좌표
z=[(i,j) for i in range(9) for j in range(9) if not a[i][j]]

# 같은 행에 중복된 숫자가 있는지 확인
def row(y,n):
 for x in range(9):
  if n == a[y][x]: return
 return 1

# 같은 열에 중보된 숫자가 있는지 확인
def col(x,n):
 for y in range(9):
  if n == a[y][x]: return 0
 return 1

# 3x3 사각형 내에 같은 숫자가 있는지 확인
def sq(y,x,n):
 r,c=y-y%3,x-x%3
 for i in range(3):
  for j in range(3):
   if a[r+i][c+j]==n: return 0
 return 1

# dfs 이용하여 탐색
def dfs(i):
 if i==len(z):
  print(*[''.join(map(str,r)) for r in a], sep='\n')
  exit()
 y,x=z[i]
 for j in range(1,10):
  if row(y,j) and col(x,j) and sq(y,x,j):
   a[y][x]=j
   dfs(i+1)
   a[y][x]=0

dfs(0)

 

 

 

대부분의 백트래킹 문제들이 DFS를 사용하는데, 꼭 DFS만 사용할 수 있는 건 아니고, 오히려 일부 문제에서는 DFS를 사용할 시 매우 비효율적이거나 무한 루프에 빠질 수도 있다. 문제의 구조를 파악하고 그에 알맞는 알고리즘을 사용하는 것이 중요하다.