[Python] 백준 15649번: 백트래킹 구현

📎 백준 15649번 풀러 가기!

15649번: N과 M (1)

문제

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

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

입력

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

출력

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

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

---

오늘은 백트래킹 문제다!

 

백트래킹 기법은 해를 찾다가 해가 아닌 것 같으면 다시 되돌아가는 방법이다.

일반적으로 DFS로 구현한다고 한다.

DFS가 가능한 모든 경우의 수를 찾는 알고리즘이기 때문!

 

개인적으로 그래프 문제에 매우 약한데,

자주 안 풀어서 ㅎㅎ... 그렇다.

아마 마지막으로 풀었던 백트래킹 문제도

알고리즘 시간에 로봇이 길 찾는 문제였나 그랬던 것 같다.

 

DFS에 대해서 오늘 어느 정도 공부했으니

앞으로 그래프 문제 자주 풀면서 익숙해져야겠다.

---

아래는 내가 구현한 코드👇

import sys

N, M = map(int, sys.stdin.readline().split())

s = list()

def dfs():
    if len(s) == M:
        print(' '.join(map(str, s)))
        return
    
    for i in range(1, N + 1):
        if i in s:
            continue
        s.append(i)
        dfs()
        s.pop()

dfs()