[백준/Python] 15652. N과 M (4)

✏️ 문제유형: DFS / 백트래킹 

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

 

 

 

 

 

✏️ 풀이 

 

처음에는 from itertools import permutations 써야지 했다가 중복 처리가 안되니까

for문으로 해보려고 했는데 시간 초과가 날 것 같고.. 이를 어쩔까 생각했다. 

 

결국 구글링...

 

그래서 알아낸 것은 DFS & 백트래킹으로 풀 수 있다는 거 

 

1로 시작한다고 하자. 그러면 1부터 N까지 큰 수 하나 중복으로 고른 게 i라고 하자. i를 배열에 저장해두고, i로 다시 가서 i부터 N까지 큰 수 하나 중복으로 고르고 반복.. 

 

이 과정을 배열의 길이가 M이 될때까지 반복하고, return해서 다른 길로 가지치기를 해야 한다. 

 

가지치기는? 백트래킹. 따라서 dfs() 호출한 뒤에 원상복구를 시켜줘야 한다. 이를 위해서 dfs() - for문에서 arr.append() -> dfs() -> arr.pop() 이렇게 된 것이다. 

 

이를 코드로 나타내면 아래와 같다. 

 

 

N,M = map(int,input().split())
arr = []
def dfs(n):
    if len(arr) == M:
        print(' '.join(map(str, arr)))
        return
    for i in range(n, N+1):
        arr.append(i)
        dfs(i)
        arr.pop()       # 백트래킹

dfs(1)