백준 15649번 파이썬 문제풀이(브루트 포스 - N과M(1)) -재귀 이용

 

코드(재귀를 이용한 코드)

 

N, M = map(int, input().split())
visited = [False] * N  # 탐사 여부 check
out = []  # 탐사한 수들을 담을 리스트 선언


def solve(depth, N, M):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, out)))  # list를 str으로 합쳐 출력
        return
    for i in range(len(visited)):  # 탐사 check 하면서
        if not visited[i]:  # 탐사 안했다면
            visited[i] = True  # 탐사 시작(중복 제거)
            out.append(i + 1)  # 탐사 내용
            solve(depth + 1, N, M)  # 깊이 우선 탐색
            visited[i] = False  # 깊이 탐사 완료
            out.pop()  # 탐사 내용 제거


solve(0, N, M)

 

# 1. visited (탐사 했는지 여부)
# 2. out (탐사 내용)
# 3. 재귀 함수 시
# - 탈출 조건 : Depth가 M일 때
# - 탐사를 안했을 경우 진행
# - Depth 탐색 전 : 탐사 시작(중복 제거), 탐사 내용 append
# - Depth 탐색 후 : 다음 탐사 준비, 탐사 내용 pop

 

-> 이 문제는 n개의 수중 m개를 뽑는 순열 문제이다. 간단히 파이썬의 라이브러리 permutations 을 이용하면 쉽게 풀 수있으나 dfs를 이용하여 재귀로 문제를 풀 경우 코드를 짤 때 생각을 많이 해봐야 한다. 중복되지 않는다면 visited 리스트를 이용할 필요가 없으나 중복된다면 visited를 이용하여 체크를 하면서 재귀를 돌아야 문제를 풀 수 있다. 재귀 관련 부분은 쉽게 늘지 않아 공부를 많이 할 필요가 있는거 같다.

 

코드 - 라이브러리 이용

import itertools

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

array = [x for x in range(1, n + 1)]

for i in itertools.permutations(array, m):
    print(' '.join(map(str, i)))