BOJ(백준) 15650번 N과 M (2) 파이썬

15650번: N과 M (2)

---

코드

import sys
r=sys.stdin.readline
N,M=map(int,r().split())
nums=[i+1 for i in range(N)]
check=[False]*N
res=[]

def dfs(cnt):
    if cnt==M:
        print(*res)
        return

    for i in range(N):
        if check[i]:
            continue

        check[i]=True
        res.append(nums[i])
        dfs(cnt+1)
        res.pop()

        for j in range(i+1,N):
            check[j]=False

dfs(0)

 

해설

이 문제 또한 파이썬 itertools 의 combinations 를 이용해 쉽게 해결이 가능하지면 backtracking의 의도와 다른 풀이이기 사용하지 않았다. 이 문제의 해결 방식은 N과 M (1) 문제인 지난 포스트 풀이와 매우 유사하다. 다만 N과 M (1) 문제에서는 1, 2와 2, 1을 다른 수열로 인정해주었지만 이 문제에서는 모든 수열을 오름차순으로 정렬하여 결과적으로 1, 2와 2, 1을 동일한 수열로 취급하게 된다. 간단하게 얘기하면 모든 경우의 순열(permutations)을 구하는 문제에서 조합(combinations)을 구하는 문제로 바뀐것이다.

이를 고려하기 위해 방문한 모든 노드들을 False 상태로 돌려 check 리스트를 리셋하지 않고 예를 들어 1, 2를 구한 경우 2, 1을 다시 구하지 않도록 i 를 포문에서 모두 순회한뒤에는 i+1 의 인덱스부터 False 로 리셋 시켜주었다.

 

결과