백준 15649, 15650 : N과 M (1), (2) (Python)

N과 M (1)

출처 : https://www.acmicpc.net/problem/15649

# 순열
n, m = map(int, input().split())
sol = list()

visited = [0] * (n+1)
def permute(n, m) :
    if len(sol) == m :
        print(*sol)
        return
    for i in range(1, n+1) :
        if visited[i] == 0 :
            sol.append(i)
            visited[i] = 1
            permute(n, m)
            sol.pop()
            visited[i] = 0
            
permute(n, m)

N과 M (2)

출처 : https://www.acmicpc.net/problem/156450

# 조합
n, m = map(int, input().split())
sol = list()

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

comb(n, m)

순열과 조합을 구현하는 문제이다. 물론 itertools를 쓰면 훨씬 간단하지만, 공부를 위해서 백트래킹으로 구현했다.

조합의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 굳이 방문했는지 여부를 저장할 필요가 없다.

그러나 순열은 한번 끝까지 탐색하면 이전 분기까지 거슬러 올라가서 다시 탐색해야하기 때문에 방문 여부를 기록해두고 거슬러 올라갈 때 방문에 체크를 해제한다.