1567 - N과 M (8) / S(3) / 백트래킹

"""
1567 - N과 M (8) / S(3)
"""
import sys

input = sys.stdin.readline

# 1. Input
N, M = map(int, input().split())
input_list = list(map(int, input().split()))
input_list.sort()
dfs_list = []

# 2. dfs function
def dfs(start):
    if len(dfs_list) == M:
        for num in dfs_list:
            print(num, end=" ")
        print()
        return

    for index in range(start, N):
        dfs_list.append(input_list[index])
        dfs(index)
        dfs_list.pop()


dfs(0)

DFS / 백트래킹 알고리즘 활용

 

1. Input

- 첫 줄 : N, M을 입력 받기

- 두번째 줄 : 입력 받은 값들을 input_list 담기

- input_list 입력 받은 값들을 오름차순으로 정렬

- dfs 함수에서 나올 값들을 담을 수 있게 dfs_list 만들기

 

2. dfs 함수

- 매개 변수 (start)

## 결과 값이 같은 값들이 나올 수 있고, 오름차순으로 출력 결과가 나와야 한다.

## 따라서 재귀 코드의 for 반복문에 들어 갈 때, start 범위를 지정하기 위해 매개변수 활용하기

 

- 종료 조건 / dfs_list의 길이가 M과 같을 때, dfs_list에 있는 값들을 출력 후 Return

 

- 재귀 코드 / input_list에 있는 값들을 조건에 맞게 dfs_list에 담아야 한다.

## start ~ N-1(마지막 인덱스) 반복문 활용하기

## dfs_list 에 같은 값이 들어갈 수 있고, 오름차순으로 값이 들어가야 한는 문제

## 따라서, dfs 함수를 재귀로 다시 실행할 때 for 반복문은 start ~ N -1 까지 체크 해야 함