백준 - N과 M(5) 15654번

문제 링크 : 백준 N과 M(5)

나의 풀이)

# 백준 N과 M(5)
# 15654번
# 백트래킹

import sys
input = sys.stdin.readline

n,m = map(int, input().split())

lst = list(map(int, input().split()))
lst.sort()

ans = []

visited = [False] * len(lst) 

def dfs(depth):
    if depth == m:
        print(*ans)
        return

    for i in range(len(lst)):
        if not visited[i]:
            visited[i] = True
            ans.append(lst[i])
            dfs(depth + 1)
            # 해당 노드에 대해서만 False 해주어서 모든 순열을 다 따질 수 있게 해준다. 
            visited[i] = False
            ans.pop()

dfs(0)

이때 다음과 같이 예제 입력이 주어지면 메모리가 어떻게 변하는 지 한번 알아보자.

4 4
1231 1232 1233 1234

1) dfs(0) 호출

visited[0] == False이므로,

ans = [1231]
visited = [True,False,False,False]

그 다음 dfs(1) 호출, ...

이런 식으로 dfs(4)까지 호출하면 다음과 같은 그림으로 표현할 수 있다.

2) dfs(4) 리턴

지역 변수 depth의 변수가 m (4)이므로, 리턴을 해준다. 그렇게 되면 앞서 진행하지 못했던 코드

            visited[i] = False
            ans.pop()

를 실행하게 된다.

3) dfs(3) 리턴

dfs(3) 에 있던 마무리 코드들을 실행하게 되고 이때 i의 값이 3이었으므로 포문을 종료하고 dfs(3)값을 리턴하게 된다.

4) dfs(3) 리턴 후 i = 2 -> 3으로 변환,다시 dfs(3) 호출

이런 식으로 진행이 된다. 나머지는 독자들이 알아서 생각해주길 바란다.

이런 식으로 코드 진행하면 주어진 수들의 순열조합을 만들 수 있다.