[Python] 백준 / silver / 15650 : N과 M (2)

문제 링크 : https://www.acmicpc.net/problem/15650

백트래킹 문제. 처음에 Python itertools 의 combinations 로 풀었는데 결과적으로 이 방법이 훨씬 쉽긴 하다. 그래도 지금은 연습이니까 백트래킹으로도 한번 더 풀어봤다.

파이썬에서 리스트를 매개변수로 넘겨주면 C++의 포인터가 전달되듯 넘겨진다. 그래서 [:] 을 활용한 깊은 복사를 사용해서 넘겨주면 메모리가 낭비되기 때문에 pop 하는 과정이 필요하다.

Combinations 풀이

from itertools import combinations
import sys

N, M = map(int, sys.stdin.readline().split())

combi = list(combinations(range(1, N+1), M))
for com in combi:
    for x in com:
        print(x, end=' ')
    print()

백트래킹 풀이

from itertools import combinations
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, sys.stdin.readline().split())

def dfs(node, comb):
    comb.append(node)
    if len(comb) == M:
        for x in comb:
            print(x, end=' ')
        print()
        return

    for i in range(node+1, N+1):
        dfs(i, comb)
        comb.pop()

for i in range(1, N+1):
    dfs(i, [])