[Baekjoon]백준 15663 N과 M (9)(실버 2) - Python

문제설명

예제

문제를 살펴보면 중복되는 수열을 출력하지 않고, M의 길이를 가진 수열을 모두 출력하는 문제이다

예전에 해당 문제를 백트래킹 알고리즘으로 해결하였던 기억이 있어서 이번에도 백트래킹을 활용하였다

우선 문제 조건에 해당하는 값들을 입력받은 후에, 수열은 오름차순으로 정렬을 수행해준다

이후 재방문여부를 확인하기 위한 리스트를 하나 만들어준 후, 결과값(수열)을 저장할 빈 리스트도 하나 만들어주었다

이후부터가 문제인데, 백트래킹 알고리즘은 항상 고민을 하고, 여러 실패를 겪으며 작성하게 되는 것 같다

 

해당 과정을 간단하게 정리하면 다음과 같다

1️⃣ sol 함수는 인자로 현재까지 선택한 개수 k를 받음
2️⃣ 만약 k가 목표 길이(length)에 도달하면, 현재까지 구성한 result 수열을 출력하고 함수를 종료(return)
3️⃣ 그렇지 않다면, for문을 돌며 다음 숫자를 선택할 후보를 탐색
4️⃣ 탐색 중에는 아직 방문하지 않은 숫자이면서 현재 depth(깊이)에서 중복되지 않는 숫자만 선택
5️⃣ 선택한 숫자를 result에 추가하고, visited[i] = True로 방문 체크를 한 뒤, 현재 숫자를 prev로 기록해 같은 깊이에서 중복 선택을 방지함
6️⃣ 재귀 호출 sol(k + 1)을 통해 다음 depth로 넘어감
7️⃣ 재귀가 끝나면 result.pop()으로 이전 상태로 되돌리고, visited[i] = False로 방문 상태도 복원

해당 과정을 통해 백트래킹 알고리즘으로 모든 조건을 만족하는 수열을 찾아가게 된다

 

그리고 이를 코드로 표현하면 다음과 같다

import sys
input = sys.stdin.readline

def sol(k):
    if k == length:
        print(*result)
        return

    prev = 0
    for i in range(len(seq)):
        if not visited[i] and seq[i] != prev:
          result.append(seq[i])
          visited[i] = True
          prev = seq[i]
          sol(k+1)
          result.pop()
          visited[i] = False

num, length = map(int, input().split())
seq = list(map(int, input().split()))
seq.sort()
visited = [False] * num
result = []

sol(0)