완전탐색 (백트래킹)

모든 경우의 수를 탐색하다 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘

백트래킹 유형을 가장 잘 보여주는 백준 온라인 저지의 9663번 N-Queen 문제를 함께 살펴봅시다.

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

N-Queens 문제의 규칙은 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다는 것이고, 우리는 4번째 줄까지 퀸을 놓는 경우의 수를 구하고 싶습니다.

예를 들어 아래와 같이 퀸의 가로에 퀸을 놓을 수 없습니다.

우리가 어떤 과정을 거쳐 판단을 내릴 수 있을지 봅시다.

이를 우리는 그래프 재귀 형태로 이해해볼 수 있는데요, (0,0)을 선택할 경우 아래 4가지 경우를 선택할 수 있습니다.

하지만 이 때, 가로/세로/대각선은 가면 안된다는 조건 때문에 (1,0)과 (1,1)은 더 가 볼 필요도 없겠죠? 이 "📌더 가볼 필요 없다"라는 점이 백트래킹에서 중요합니다. 가지치기를 통해 더이상 조건에 맞지 않으면 가지 않는 것이 백트래킹의 큰 특징입니다.

이후 그래프를 더 파악해봅시다. (1,2)를 탐색해본 후더이상 갈 수 없다는 것을 알았습니다.

이런 경우 다시 이전으로 돌아와 다른 경우 즉 (1,3)을 탐색하기 시작합니다. 이렇게 📌조건에 맞지 않으면 이전으로 돌아오는 것이 백트래킹의 두번째 중요한 특징입니다.

(1,3)->(2,1)로 선택했을 때에도 안 되는 경로임을 알았습니다.

이 때는 이제 어디로 가야 할까요??

...

맞습니다! 바로 (0,1)로 가야 합니다.

다음과정을 전체적으로 확인하면 다음과 같습니다. "가지치기", "이전으로 돌아가서 다른 선택지 확인"에 초점을 두고 파악해봅시다!

위 동영상에서도 볼 수 있듯이, 백트래킹은 재귀함수로 구현합니다.

재귀함수의 핵심은 호출과 반환입니다.

Windows 창에서 오류로 인해 여러 창들이 계속해서 보여질 때 한 창이 다른 화면을 호출하는 것을 반복하여 다음과 같은 모습을 보인 적이 있나요? 이 때 가장 안쪽에 있는 창부터 반환시켜야 가장 상위에 있는 창까지 차례대로닫을 수 있습니다.

재귀함수의 이러한 특성을 이용하여, 아래 코드에서는 어떤 때에 n_queens() 함수를 다시 호출하는지, 또 어떤 때에 n_queens() 함수의 결과값을 반환하는지에 주의하여 봅시다.

n = int(input())

ans = 0
row = [0] * n

def is_promising(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            #+나 X 형태의 경우는 갈 수 없다. 가지치기
            return False
    return True

def n_queens(x):
    global ans
    if x == n:
        ans += 1
        return
    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(ans)

위 코드를 간단히 확인해보면 is_promising함수는 (1,0) (2,0) 등 세로의 경우와 (1,1)과 (2,2)의 대각선 경우를 가지치기하는 코드입니다.

이후 n_queens는 이미 재귀함수로 짜여져 있어 if문에 적용이 되지 않으면 자동적으로 이전 경우로 돌아가 다른 경우를 탐색함을 알 수 있습니다.

더 풀어볼 문제로는 N과 M 시리즈가 있습니다.

https://www.acmicpc.net/workbook/view/2052www.acmicpc.net

백트래킹을 이해해보며 추가적인 내용을 익혀봅시다! 위 동영상처럼 그림을 그려보면 이해에 도움이 됩니다.

N과 M 시리즈에서 5번 문제를 같이 볼까요?

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

백트래킹의 전형적인 로직으로, 아래 코드에서 pop시키는 과정이 arr에서 7을 pop시키는 과정이고, 이후 다시 다음 숫자8을 그 자리에 넣게 됩니다.

def go(arr):
    if len(arr) == m:
        print(' '.join(map(str,arr)))
        return
    for i in range(n):
        if len(arr)==0 or List[i] not in arr:
            arr.append(List[i])
            go(arr)
            arr.pop()
            
n, m = map(int,input().split())
List=list(map(int, input().split()))
List.sort()
go([])

풀어볼 문제

아래 문제들을 보면 알 수 있듯이, N이 10, 15, 20 이하임을 알 수 있습니다. 만약 N이 10, 15, 20 이하라면 우선적으로 완전탐색과 백트래킹을 의심해보는 것이 좋은 접근입니다.

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

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

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