문제
문제 링크 : 백준 15650
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근
dfs에서 살짝 변형해주면 된다고 생각했다.
왜냐하면 dfs(깊이 우선 탐색)을 통해 결국 1부터 주어진 n까지는 전부 확인해야하기 때문이다.
대신 m의 길이가 주어지기 때문에 재귀를 통해 dfs를 실행하더라도 해당 재귀는 m길이만큼이 되면 중단한다.
풀이
기본적으로 1부터 순차적으로 접근해야하기에 dfs(1)로 시작한다.
- 매번 현재 dfs에 들어온 수부터 n까지 반복한다.
- 출력을 위한 배열(s)에 현재 수가 들어있지 않다면 추가하고 dfs(i)를 한다.
- 재귀를 하는데 s의 개수가 m과 같다면 출력하고 재귀 중단한다.
- 중단하면 s의 마지막 수를 비운다.
- 다 비울 경우 다음 2번으로 돌아가 다시 앞 자리 수부터 시작한다.
그리고 접근하고 풀이한 방식을 예제2 예시로 표현해 봤다. 
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 15650
import sys
def dfs(c):
if len(s) == m:
for j in s:
print(j, end=" ")
print()
return
for i in range(c, n + 1):
if i not in s:
s.append(i)
dfs(i)
s.pop()
input = sys.stdin.readline
n, m = map(int, input().split())
s = []
a = []
dfs(1)
느낀점
dfs의 응용버전이라고 볼 수 있는 백트래킹을 다시 해보니깐 감이 처음에는 오지 않았는데
끝까지 검색하지 않고 분기 설정을 통해 더 이상 진행하지 않는 점에서 효율적인 것 같다.
소소한 팁이라면 6~8번까지의 출력코드는 아래의 코드를 통해 간략하게 쓸 수 있다는 점을 찾았다..ㅎㅎ
1
print(' '.join(map(str,s)))