[Python] N과 M (4) - 백준 (DFS)

해당 글은 백준 15652번 'N과 M (4)' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

설명

1에서 N까지의 M개의 고른 수열을 구하는 문제이다.

 

DFS로 1~4개의 숫자로 2개의 고른 수열을 고른다고 하면,

첫번째 수가 1일 때 1~4, 2일 때 2~4, 3일 때 3~4, 4일 때 4까지의 값을 출력해야 한다.

리스트에 for문을 이용해서 수를 추가해주고, 리스트의 갯수가 2개가 아니라면 수를 추가해서 DFS를 진행한다.

 

항상 DFS로 길찾기 비슷한 문제를 풀었었는데, 이런 방식의 DFS로 접근하니까 신선하였던 것 같다.

 

 

코드

n, m = map(int, input().split())
arr = []

def dfs(start):
    if len(arr) == m:
        print(*arr)
        return
    for i in range(start, n+1):
        arr.append(i)
        dfs(i)
        arr.pop()
dfs(1)