백준 문제 중 15649번, 백트래킹, ‘N과 M(1)’

백준 문제 중 15649번

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

문제

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

풀이

브루트 포스로도 접근이 가능한 문제이지만 DFS로 풀어야 시간을 단축 할 수있다.

처음엔 수열이 DFS로 접근이 가능하다는 사실을 알기 힘들다. 예를 들어 [1,2,3]으로 만들수 있는 수열을 순서대로 만들어 가며 나열 해보자.

1. 처음 부모노드는 []이고 자식은 1, 2, 3을 가지고 있다.

2. DFS 이므로 1, 2, 3 중 1을 택해 탐색한다. 이때의 수열은 [1] 이다.

3. [1]을 부모로하는 자식은 이미 선택된 1을 제외하고 2, 3을 가지고 있다.

4. DFS 이므로 2, 3 중 2를 탐색하고, 이때의 수열은 [1,2] 이다.

5. [1,2]을 부모로 하는 자식은 1, 2 를 제외하고 3을 가지고있다.

6. DFS 이므로 3을 탐색하고 탐색을 완료하고 [1,2,3] 을 반환한 후 3번 과정으로 돌아가자.

7. 3번 과정의 2, 3 중 2는 이미 탐색했으므로 다음 탐색은 3 을 택한다.

8. [1,3]을 부모로 하는 자식은 1,3 을 제외하고 2을 가지고있다.

9. [1,3,2]를 완성하며 4번 과정으로 돌아간다…

10. 재귀로 DFS를 모두 완료하면 가능한 모든 수열을 완성 할 수 있다.

위와 같은 과정으로 모든 수열을 구할 수 있지만 이문제는 모든 수열을 구할 필요는 없고 길이 M일때 바로 DFS를 종료 시킬 수 있는 조건이 있으므로 백트래킹이 가능한 DFS 문제이다.

이를 코드로 구현하면 다음과 같다.

from typing import List

n, m = map(int,input().split())

nums =list(range(1,n+1))

discovered = []

def dfs(nums:List[int])->None:

     # discovered의 길이가 m과 같다면 바로 출력
    if len(discovered) == m:
        print(*discovered)
        return
    
     # nums안의 각각을 시작 노드로 하는 DFS 탐색
    for n in nums:

         # 이미 수열에 추가된 n이라면 불가능
        if n not in discovered:

             # 이전 수열에 n을 추가하고 DFS 시작
            discovered.append(n)
            dfs(nums)
             # 반드시 pop을 해줘야 다음 자식노드를 방문할 수 있다,
            discovered.pop()

dfs(nums)


        

4 4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1