백트래킹 : 재귀를 활용한

15654번 N과 M (5) https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

음... 완전탐색을 위해서 for문을 중첩으로 돌려야 하는데

for 문을 중첩시키는 횟수를 입력받아서 능동적으로 변경해야 하는 상황이었다. 이ㅓㄱㄹ 어떻게 하나..?

 

했더니 답은 재귀였다.

 

즉, 입력값에 맞춰서 for문의 중첩횟수를 설정해줘야 하는 경우라면

재귀함수가 적합하다

 

import sys
N, M = map(int, input().split())
nums = sorted(list(map(int, sys.stdin.readline().split())))

output = []
visited = [False]*N


def solve(depth, N, M):  # reculsive
    # stop condition
    if depth == M:
        print(' '.join(map(str, output)))
        return

    for i in range(N):
        if not visited[i]:  # 방문기록 점검, 일종의 그래프 탐색
            visited[i] = True
            output.append(nums[i])
            solve(depth+1, N, M)
            output.pop()
            visited[i] = False


solve(0, N, M)

일종의 그래프 탐색과도 같다. (깊이 우선?)

visited를 통해 방문한 숫자를 확인해준다 -> 중복을  허용하지 않는 순열이기 때문에

 

 

너무 명쾌한 풀이라서 행복했다.