백트래킹 - joi0104/BOJ GitHub Wiki

정의

  • 모든 조합 중 특정 조건을 만족하는 조합들을 살펴보는 알고리즘
  • 조건만족문제(CSP)에서 일반적으로 쓰이는 알고리즘

구현

  • 보통은 재귀를 사용한다. 문제를 작은문제로 나누고 각 작은 문제에서 조건을 만족할 경우 다음 작은 문제를 재귀적으로 호출할 수 있도록 구현한다.
  • 이전상태로 돌아가고 싶다면 이번상태에서 바꿨던 변수들을 재귀 이후에 돌려놓아야 한다. 따라서, 변수 값 자체를 바꾸기보다 재귀함수의 파라미터에 값을 바꿔서 전달하는것을 권유한다.
x += 1
backtracking(x)
x -= 1

backtracking(x)

대표적인 문제: N-Queen 문제

문제 정의

N*N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까?

구현

한 칼럼에 Queen을 쭉 놓은 뒤, 서로 공격하지 않는 경우를 확인한다. 조건을 만족하는 칼럼만 다음 칼럼을 고려한다. 다시 다음 칼럼에서 Queen을 쭉 놓은 뒤, 서로 공격하지 않는 경우를 확인한다. 이를 반복한다. 재귀의 깊이(칼럼의 수) 가 N이 되면 재귀호출을 중지한다.

코드

def adjacent(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x):
    global result

    if x == N:
        result += 1
        return

    else:
        for i in range(N):
            row[x] = i
            if adjacent(x):
                dfs(x + 1)


N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)
⚠️ **GitHub.com Fallback** ⚠️