15663: N과 M (9)

• 탐색한 노드 (visited node)를 저장하기 위한 자료구조로 visit list를 사용 (index별로 true, false가 저장됨)
• 위의 그림에서 보이는 것처럼 같은 depth에서 값이 같은 경우는 pruning을 해야하기 때문에 flag 변수를 이용해 같은 depth에서 값이 같은 node를 방문하지 않도록 구현함

import sys

N, M = map(int, input().split(' '))
tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
tmp.sort()

visit = [False for _ in range(N)]
result = []

def dfs():
    if len(result) == M:
        print(" ".join(map(str, result)))
        return
    flag = 0
    for i in range(N):
        if not visit[i] and flag != tmp[i]:
            visit[i] = True; result.append(tmp[i])
            flag = tmp[i]
            dfs()
            visit[i] = False; result.pop()

dfs()