[Python] Baekjoon - 15654. N과 M (5)

백준의 N과 M 시리즈는 N개의 숫자가 포함된 수열에서 M개를 고르는 문제이다. 매번 조건이나 규칙이 변경되어 총 12개의 문제가 있다. 이번 문제는 사전 순으로 증가하는 순서로 출력하는 문제이며 백트래킹을 이용하여 풀 수 있다. 난이도는 실버 3이다.

 

백준 15654번 N과 M (5) 문제 정보

알고리즘 분류

- 백트래킹

난이도

- 실버 3

 

N과 M (5) 문제 요약

중복 없는 N개의 숫자 중 M개를 선택하여 사전 순으로 증가하는 순서로 출력하는 문제다.

 

문제 풀이 과정

DFS를 이용하여 현재까지 방문하지 않은 숫자를 방문하고, M개의 숫자가 선택되면 출력한다. 사전 순으로 출력하기 위해 초기에 입력받은 수열을 정렬 후 수행한다.

 

코드

import sys


def dfs(cnt):
    global N, M, num_list, visited

    if cnt == M:
        sys.stdout.write(' '.join(answer) + '\n')
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = 1
            answer.append(str(num_list[i]))
            dfs(cnt+1)
            visited[i] = 0
            answer.pop()


if __name__ == '__main__':
    N, M = map(int, input().split())
    num_list = sorted(list(map(int, sys.stdin.readline().split())))
    visited = [0 for _ in range(N)]
    answer = []

    dfs(0)