[BOJ] N과 M (9)

---

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ans = []
v = []
visited = [False]*n
def dfs():
    if len(ans) == m:
        print(' '.join(map(str, ans)))
        return
    
    prev = 0    # 깊이가 달라질 때마다 초기화
    for i in range(n):
        # 방문하지 않았고
        # 이전에 같은깊이의 같은 숫자를 쓰지 않은 경우
        if not visited[i] and prev != arr[i]:   
            ans.append(arr[i])
            visited[i] = True
            prev = arr[i]
            dfs()
            visited[i] = False
            ans.pop()

dfs()

결과

풀이 방법

• 백트래킹 문제이다.
• 중복되는 수열을 거르기 위해 이전의 N과 M 문제에서 한 가지 조건을 더 추가해야 한다
• 현재 깊이에서 이전에 사용했던 숫자를 나타내는 prev 변수를 도입하여, 현재 수열에 추가할 숫자가 이전에 사용한 숫자(같은 깊이에서)가 아닌 경우인지를 추가적으로 확인한다
• 깊이가 달라질 때마다 prev = 0 으로 초기화해야 한다.

---