[DFS/BFS/완전탐색] 15651번 - N과 M (3)(DFS, 백트래킹)

[백준] 15651번 - N과 M (3)

풀이 시간: 5분 이내

 

1) 문제 해결 아이디어

1부터 N까지의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래 조건에 따르면 중복 순열을 구하는 문제다.

 

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 permutations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 중복 순열을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다.

 

중복 순열을 구할 때는 dfs 인자로 깊이(depth)만 넘겨주면된다!!

이전 선택 여부를 확인하지 않아도 된다!!

 

2) 소스코드

# 중복 순열
n, m = map(int, input().split())   
temp = []  # 수열을 담을 곳
 
# DFS
def dfs(depth):
  # 길이가 m이 되었다면
  if depth == m:
    print(*temp)
    return
  # 1 ~ n 중에서 1개 뽑기
  for i in range(1, n + 1):
    temp.append(i)
    dfs(depth + 1)
    temp.pop()
dfs(0)