[백준] 15663 N과 M(9) (Python)

문제 보기

문제 바로가기

풀이 코드

def solution():
    check = 0
    if len(answer) == m:
        print(*answer)
        return
    for i in range(n):
        if check != num[i] and visited[i] == 0:
            answer.append(num[i])
            visited[i] = 1
            check = num[i]
            solution()
            answer.pop()
            visited[i] = 0


n, m = map(int, input().split())
num = sorted(list(map(int, input().split())))
visited = [0] * n
answer = []
solution()

먼저 num정보들을 넣은 리스트를 정렬한 후, 중복값도 제거하고 visited로 확인도 해주어야 한다. [1, 1]이나 [7, 7]과 같은 값들이 출력되면 안되는걸로 보아서 재귀를 돌기 전에 값을 기억해둔 후, append하기 전에 i번째 인덱스의 값이 일치한다면(중복된다면) 재귀함수를 돌지 않고 일치하지 않아야만 재귀함수를 통해 값을 append할 수 있도록 한다.
이 문제는 일반적인 백트래킹 문제들에서 많이 보던 유형 같았다!!
N과 M문제 시리즈 중에서도 조금 생각을 많이 해봤어야 하는 문제다!