[Python] 15649번 N과 M (1)

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

15649번: N과 M (1)

---

 

22/11/30

 

 

백트래킹의 기초적인 문제로, 단계별로 풀어보기에서 풀어볼 수 있다.

---

 

문제 접근 방식:

 

 

백트래킹은 주로 재귀+가지치기로 접근이 되어진다.

 

말 그대로 Backtrack이기 때문에, 쭉 갔다가 다시 돌아오는 작업이 필요하다.

 

때문에 깊이 있게 들어가는 dfs탐색으로 대부분의 문제가 풀린다.

 

dfs는 스택을 이용할 수도 있고, 재귀를 이용할 수도 있지만, 일반적으로 재귀를 이용한 구현이 많으므로, 백트래킹도 재귀를 통해 구현이 될 때가 많다.(물론 다른 방법으로도 구현할 수 있다.)

 

 

문제를 보면, 중복 없이, 사전 순으로 증가하도록 출력해야 한다.

 

때문에 나는 중복이 없다는 말에 의거하여, 중복을 체크해주는 visited 배열을 선언해주어서 이미 숫자 리스트에 담겨 있는 숫자들을 다시 리스트에 넣지 않도록 해주었다.

 

재귀를 통해 담다가 결국 M개의 숫자를 리스트에 담게 되면, 그 리스트를 출력하도록 해주었다.

 

Backtrack이기 때문에, 재귀 호출의 끝에 리스트에 담았던 원소를 다시 빼는 작업 또한 진행하였다.

 

사실은 파이썬의 경우, 이 문제를 백트래킹으로 일일이 구현하지 않아도 itertools의 permutations함수가 있기 때문에 이를 사용하여 문제를 쉽게 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 15649번 N과 M (1)
# 백트래킹
def dfs(count, num_arr):
    if count == M:
        print(*num_arr)
        return
    for i in range(1, N+1):
        if visited[i] == 0:
            num_arr.append(i)
            visited[i] = 1
            dfs(count+1, num_arr)
            num_arr.pop()
            visited[i] = 0

N, M = map(int, input().split())
visited = [0 for _ in range(N+1)]
dfs(0, [])

from itertools import permutations
N, M = map(int, input().split())
for tpl in permutations(range(1, N+1), M):
    print(*tpl)