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

[백준] 15652번 - N과 M (4)

풀이 시간: 5분 이내

 

1) 문제 해결 아이디어

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

 

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

 

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

 

중복 조합을 구할 때는 이전에 선택한 값보다 작은 값을 골라서는 안되므로 dfs 인자로 깊이(depth)에 탐색시작값(idx)를 추가로 넘겨주어야 한다!!

이전 선택 여부를 확인하지 않아도 된다!! 탐색 시작값은 그대로 넘겨주는 것을 잊지말자!

 

2) 소스코드

# 중복 조합
n, m = map(int, input().split())   
temp = []  # 수열을 담을 곳
 
# DFS(깊이, 탐색시작값)
def dfs(depth, idx):
  # 길이가 m이 되었다면
  if depth == m:
    print(*temp)
    return
  # 1 ~ n 중에서 1개 뽑기
  for i in range(idx, n + 1):
    temp.append(i)
    dfs(depth + 1, i)  # 탐색 시작값은 그대로 넘겨줌
    temp.pop()
dfs(0, 1)