[PS] BOJ 15663 / N과 M (9)

Minjun Kim

26 Jun 2025 • 4 min read

문제 링크: https://www.acmicpc.net/problem/15663

Thumbnail: Photo by Ronit Shaked (Unsplash)

N과 M은 다시 말하지만 유명한 백트래킹 시리즈입니다.

풀이

기본적인 풀이는 15652번 문제(N과 M (4))와 동일합니다. 하지만, 입력으로 주어지는 수열에 중복되는 수가 존재하며, 출력할 결과는 사전순으로 정렬되어야 하고 중복이 허용되지 않습니다.

중복 방지하기

결과를 저장할 때, 일일히 결과 배열을 확인하며 기존에 입력되었는지 확인하는 방법은 별로 적합하지 않습니다. 이런 경우에 '집합(set)' 자료구조를 활용할 수 있습니다.

집합은 중복되는 원소를 가지지 않는 자료구조로, 우리는 단순히 집합에 값을 추가하기만 하면 그 과정에서 중복되는 값은 배제됩니다.

아래 코드에서는 output 배열에 백트래킹 과정을 기록하고, result 집합에 결과를 저장했습니다.

N, M = map(int, input().split())
A = list(map(int, input().split()))
output = [0 for _ in range(M)]
result = set()

def dfs(depth):
    if depth == M:
        result.add(output)
        return
    
    for i in range(N):
        ...

dfs(0)

집합 사용하기

결과 정렬하기

처음에는 백트래킹 결과를 문자열로 변환해 집합에 저장한 후 정렬했는데, 바로 틀렸습니다를 받았습니다.

찾아보니, 이는 문자열의 정렬과 숫자의 정렬이 다르기 때문에 일어나는 현상입니다.
단순한 예시로 알아봅시다.

sorted([1, 3, 2, 11])
>>> [1, 2, 3, 11]
sorted(["1", "3", "2", "11"])
>>> ["1", "11", "2", "3"]

문자열의 사전 순 정렬 방식은 숫자의 정렬 순서와 다르다.

따라서, result 집합에 output배열의 원소를 담은 튜플을 저장하는 방식으로 구현 후 집합을 정렬했습니다.

def dfs(depth):
    if depth == M:
        result.add(tuple(output))
        return
    ...

for r in sorted(result):
    print(" ".join(map(str, r)))

튜플로 output을 변환 후 저장한다.

잘못된 결과 배제하기

지금까지 작성한 코드를 돌아봅시다.

input = open(0).readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
output = [0 for _ in range(M)]
result = set()

def dfs(depth):
    if depth == M:
        result.add(tuple(output))
        return
    
    for i in range(N):
        output[depth] = A[i]
        dfs(depth + 1)
        output[depth] = 0

dfs(0)

for r in sorted(result):
    print(" ".join(map(str, r)))

단순히 위 코드대로 백트래킹을 진행하면, 결과 수열에 특정 숫자가 주어진 것 보다 더 많이 포함되는 경우가 발생합니다. 따라서, 우리는 결과 수열에 각각의 숫자가 몇개 포함되는지 파악해야 합니다.

먼저, 입력으로 받은 수열에 각 숫자가 몇 개씩 포함되었는지 파악합니다. 이번에는 파이썬의 내장 모듈인 collections에 구현된 Counter 객체를 사용했습니다.

from collections import Counter

original_counter = Counter(A)

입력 수열의 원소 개수 파악하기

다음으로, 결과 수열에 포함되는 각 숫자의 개수를 계산할 Map 자료구조를 하나 선언합니다. 파이썬은 dict를 사용하면 됩니다.

output_counter = {key: 0 for key in original_counter.keys()}
# original_counter에 저장된 각 키 값에 대해 0을 값으로 가지는 Map 선언

결과 수열에 포함되는 숫자의 개수를 셀 변수 선언하기

이후, 백트래킹을 진행할 때 결과 수열에 새로 포함되는 숫자의 개수를 파악해주면 됩니다. 이는 결과 수열을 저장하는 배열 output에 원소를 추가하고 제거하는 과정과 유사합니다.

def dfs(depth):
    if depth == M:
        result.add(tuple(output))
        return
    
    for i in range(N):
        if output_counter[A[i]] < original_counter[A[i]]:
            output[depth] = A[i]
            output_counter[A[i]] += 1
            dfs(depth + 1)
            output[depth] = 0
            output_counter[A[i]] -= 1

결과 수열에 새로 숫자가 포함되면 output_counter 갱신하기

이 과정을 통해, 특정 숫자가 입력 수열에 주어진 것보다 더 많이 포함되는 경우를 배제할 수 있습니다.

전체 코드

from collections import Counter
input = open(0).readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
output = [0 for _ in range(M)]
result = set()
original_counter = Counter(A)
output_counter = {key: 0 for key in original_counter.keys()}

def dfs(depth):
    if depth == M:
        result.add(tuple(output))
        return
    
    for i in range(N):
        if output_counter[A[i]] < original_counter[A[i]]:
            output[depth] = A[i]
            output_counter[A[i]] += 1
            dfs(depth + 1)
            output[depth] = 0
            output_counter[A[i]] -= 1

dfs(0)

for r in sorted(result):
    print(" ".join(map(str, r)))

solution.py