[백준-실버3] 15650번 N과 M(2) (파이썬, 백트래킹, DFS)

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

15650번: N과 M (2)

 

<복습 체크>

22/03/05
O

<내 코드1>

- N과 M(1)번 문제가 순열이었다면 (순서를 고려하기 때문에 1 2 <--> 2 1 다른 값으로 취급)

- 이번 문제를 조합이라 1 2를 출력했으면 2 1은 출력하면 안된다.

- 따라서 이번 문제는 dfs에 start 파라미터를 이용하여 중복을 허용하지 않는다.

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

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

 

<내 코드2>

- N과 M(1)번 문제랑 다른 점은 중복을 허용하지 않는다 (ex (1,2) <-> (2,1) 중 (1,2)만 허용)

n, m = map(int, input().split())

arr = [0]*m
isused = [False]*(n+1)

def func(k):
    if k==m:
        for i in range(m):
            print(arr[i], end = ' ')
        print()
        return
    for i in range(1,n+1):
        if isused[i] == False:
            arr[k] = i
            isused[i] = True
            
            func(k+1)
            #이 부분에서 i를 제외한 숫자의 isused를 False로 만들어줌
            for j in range(i+1,n+1):
                isused[j] = False
            
func(0)