[백준 15649 | python] N과 M (1) (백트레킹)

• 문제 링크: https://www.acmicpc.net/problem/15649
• 백준 15649번
• 파이썬

 

Q1) 문제를 어떻게 이해했나요?
A1) 1부터 N까지의 수 중에서 M개를 중복 없이 뽑아서 만든 수열을 모두 출력해야 해요.

Q2) 문제를 어떻게 풀 예정인가요?
A2)
DFS(백트래킹)을 사용해 수열을 하나씩 만들어가며 탐색합니다.
이미 선택한 숫자는 visited 배열로 중복 선택을 막습니다.
수열의 길이가 M에 도달하면 출력합니다.
사전 순 출력을 위해 숫자 1부터 N까지 오름차순 탐색을 합니다.

 

 

def solution(N, M):
    visited = [False] * (N + 1)

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

        for i in range(1, N + 1):
            if not visited[i]:
                visited[i] = True
                dfs(path + [i])
                visited[i] = False  # 백트래킹

    dfs([])

# 예시 입력
N, M = map(int, input().split())
solution(N, M)

 

• itertools.permutations

permutations(iterable, r)는 iterable에서 r개의 요소를 뽑아 만들 수 있는 모든 순열을 반환해요.
중복 없이 뽑기 때문에, 이 문제의 조건과 딱 맞아요.

 

from itertools import permutations

N, M = map(int, input().split())

for p in permutations(range(1, N + 1), M):
    print(' '.join(map(str, p)))