해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 15649번 N과 M(1) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다.

2. 재귀함수를 이용하고, 그 재귀함수에는 숫자의 개수를 전달하여, 그 개수가 m개 이면 리스트의 내용을 출력하도록 합니다.

3. 재귀함수에서 개수가 m개가 아니라면, n까지의 숫자들을 확인하고, 방문하였는지 체크하여, 방문하지 않은 숫자를 기준으로 가지치기(재귀함수 호출)를 합니다.

N = 4, M = 3인 경우, 위와 같이 깊이우선탐색의 순서대로 방문하여, 리스트를 출력하는 방식으로 합니다. 

위 그림에서 2, 3, 4가 루트인 경우에도 동일한 방식으로하여 구하면 됩니다. 

전체 코드

N, M = map(int, input().split())
visited = [False] * N
lst = []

def dfs(depth):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            lst.append(i+1)
            dfs(depth+1)
            visited[i] = False
            lst.pop()