[백준] 15649 N과 M(1)

💡 문제

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

15649번: N과 M (1)

 

💡 정답

n, m = map(int, input().split())
s=[]

def dfs() :
    if len(s) == m:
        print(' '.join(map(str,s)))
        return

    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

 

💡 풀이

 

이 문제는 Python을 사용한다면, itertools.permutations()함수를 이용해 답을 바로 구할 수 있다.

Python에서 손쉽게 순열, 조합 등을 구할 수 있는 함수를 제공하기 때문이다.

하지만, 그것은 백트래킹을 연습하고자 하는 이 문제의 의도와 다르므로 사용하지 않도록 한다.

 

백트래킹이란?

백트래킹은 DFS(Depth-Fist Search, 깊이 우선 탐색)의 방식을 기반으로, 불필요한 경우를 배제하며 원하는 해답에 도달할 때까지 탐색하는 전략이다.

 

백트래킹은 기본적으로는 모든 경우의 수를 탐색한다는 브루트 포스 전략을 취하지만, 처리 속도를 향상시키기 위한 가지치기(Pruning)가 중요한 역할을 한다. 백트래킹에서 가지치기를 잘 할수록 불필요한 경우가 제거되어 처리 속도가 많이 향상된다.

for i in range(1, n+1):
    s.append(i)
    dfs()
    s.pop()

해당 경우의 수를 스택에 추가하고, 동작(여기서 dfs()함수)이 끝난 후에는 다시 스택에서 빼내는 작업(Pop)이 필요하다. 정상적으로 이전의 상황으로 돌아올 수 있기 때문이다.