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

Thumbnail: Photo by Brett Jordan (Unsplash)

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

풀이

백트래킹 (DFS)

백트래킹도 결국은 DFS입니다. 다만, 분기에 진입하기 전에 조건에 맞는지 아닌지를 미리 판단해, 적합하지 않은 분기라면 진입하지 않고 건너뛴다는 차이점이 있습니다.

이번 문제에서는 \(N\)과 \(M\), 그리고 \(N\)개의 수로 구성된 배열 \(A\)를 입력받아, \(A\)에서 서로 다른 수를 \(M\)개 꺼내어 만들 수 있는 모든 조합을 출력하는 문제입니다. 다만, 출력된 결과는 반드시 사전 순이어야 합니다.

사전 순 출력?

사전 순으로 결과를 출력하려면, 결과를 어떻게 만드는지 그 과정을 지켜보면 됩니다.

DFS 부분에서는 배열의 앞부터 뒤까지 순회하며, 아직 사용하지 않은 원소를 결과 배열에 넣고 있습니다. 다시 말해, 배열 \(A\)가 이미 사전 순으로 정렬되어 있다면 DFS로 출력되는 모든 결과들은 자연스럽게 사전 순으로 나오게 됩니다.

전체 코드

input = open(0).readline
N, M = map(int, input().split())
A = sorted(map(int, input().split()))

visited = [False for _ in range(N)]
result = []
def dfs(depth):
    if depth == M:
        print(" ".join(map(str, result)))
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            result.append(A[i])
            dfs(depth + 1)
            visited[i] = False
            result.pop()

dfs(0)