[알고리즘] 백트래킹

오늘 백트래킹 강의를 듣고 개념을 이해하려고 했지만 어려움이 있어서

블로그에 정리하며 다음에 쉬운 문제부터 풀어보려고 한다.

 

백트래킹이란?

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는데

불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다고 해서 가지치기라고 부른다.

코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적으로 사용하면 시간적 비용을 아낄 수 있다.

 

물론 이런식으로 봐도 잘 모르겠어서 문제를 풀어보려고 하는데

백트래킹에서 가장 유명한 문제는 nqueen문제라고 퀸을 체스판 위에 서로 공격당하지 않는 위치에 두는 문제이다.

하지만 이 문제를 풀다가 막혔기 때문에 예시로 든 문제중 가장 쉬운 문제인 수열 문제를 풀어보려고 한다.

백준 15649 - N과 M (1) 

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

여기서 중복되는 수열을 출력하면 안되기 때문에 중복되는 경우의 수를 제거하는 백트래킹 문제이다.

import sys

N, M = map(int, sys.stdin.readline().split())
result = []
check = [False]*(N+1)

def recur(num):
    if num == M:
        print(' '.join(map(str, result)))
        return

    for i in range(1,N+1):
        if not check[i]:
            check[i] = True
            result.append(i)
            recur(num+1)
            check[i] = False
            result.pop()

recur(0)

이 코드가 재귀함수를 사용해서 문제를 해결하는 백트래킹 로직인데

check에 N+1을 하는 이유는 index는 0부터 시작하기 때문에 check[i]를 할 때, i값에서 계속 1을 빼줘야하는

수고가 있기 때문에 더욱 간단하게 check의 0번째 인덱스를 사용하지 않기로 하고 값을 하나 늘려주었다.

 

종료 조건은 num이 M이 되었을 때 원하는 갯수가 되었기 때문에 print를 하고 다음 for문으로 돌아간다.

for문에서는 check를 통해 이미 방문했는지를 확인하고 방문을 안했으면 check[i]를 True값으로 바꾼 뒤에

result에 i값을 넣어주고 재귀함수를 돌려준다.

처음에 result.pop을 넣어주지 않아서 에러가 떴는데 재귀함수를 돌리는 중에 result가 1,2 가 있는 상태에서

3이 들어가면 함수를 계속 돌려도 [1,2,3]에서 바뀌지 않기 때문에 리스트를 돌리는 중에 넣은 숫자는

마지막에 코드를 종료하기 전에 빼줘야 한다.

 

이제 num을 0부터 시작해서 재귀함수를 돌려주면 된다.

Python에는 itertools 이용해서 순열 문제를 간단하게 풀 수 있지만 백트래킹 로직을 이해하기 위해서

직접 코드를 구현해가며 풀어보았다. (itertools를 이용해서 푼 코드는 다음과 같다.)

import sys
import itertools

N, M = map(int, sys.stdin.readline().split())
result = []
for i in range(1, N+1):
    result.append(i)
nPr = itertools.permutations(result, M)
for perm in nPr:
    print(" ".join(map(str, perm)))

훨씬 간결하지만 로직을 이해하지 않고 쓰는 모듈은 도구를 쓸 줄 모르고 들고있기만 하는 것과 같다.

다음날에는 nqueen문제에 도전해보고 다른 백트래킹 문제도 같이 풀어봐야 겠다.