백준 15649번 문제 바로가기

permutations을 이용한 풀이

처음에는 보자마자 itertools에서 permutations을 불러와서 사용했다. 간편하고 빨라서 만족하면서 제출했는데 역시나 정답! 하지만 이 문제를 분석하면서 알고리즘 분류를 봤더니 백트래킹이라는 처음 보는 개념을 가리키고 있었다. 백트래킹에 대한 개념을 알아보고 그 풀이로 다시 풀어보기로 했다.

# 입력
import sys
from itertools import permutations
n,m = map(int, sys.stdin.readline().split())
arr = [i+1 for i in range(n)]

# 처리
for ans in permutations(arr, m):
    print(*list(ans))

백트래킹(backtracking)이란?

백트래킹은 간단하게 말하자면 가지치기라고 말할 수 있다. DFS의 경우 모든 가지를 다 커버할 떄까지 탐색을 진행하지만, 백트래킹의 경우 특정 조건을 만족시키면 뒤로 돌아가서 다른 경우의 수를 찾아나간다. 이런 특징 때문에 Back+Tracking이라는 이름을 가지게 되었다. 백트래킹에 대한 추가 설명은 이 분이 정말 잘 설명해주셨으니 참고 바란다. (이거보다 더 잘 설명할 자신이 없다…)

backtracking을 이용한 풀이

구현하는 과정이 생각보다 어려워서 많은 시간을 소요했다… 사실 permutations 방식이 너어어어무 편해서 다른 풀이를 시도하고 싶지 않기도 했다 ㅋㅋ

# 입력
import sys
n,m = map(int, sys.stdin.readline().split())
ans = []

# 처리
def backtrack():
    if len(ans) == m:
        print(*list(map(str, ans)))
        return
    for i in range(1, n+1):
        if i not in ans:
            ans.append(i)
            backtrack()
            ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack)

backtrack()