백준 - 15649번

DFS를 이용한 순열 알고리즘

 

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            arr.append(i + 1)
            #print("arr은",arr)
            dfs(cnt + 1)
            visited[i] = 0
            #print("visit 다음 arr은", arr)
            arr.pop()
            #print("pop다음 arr은", arr)

dfs(0)

한줄 한줄 보면서 이해하기 위해서 썼던 print문을 주석으로 달아 놨다.

이해가 안가는 부분이 마지막 [1]의 pop은 어떻게 빠지는가

어떻게 자동으로 2로 바뀌는가에 대한 부분인데 좀 더 공부가 필요하다.

visited[i]를 초기화 하지 않으니깐 1에대해서만 진행되고 멈춘다.

 

from itertools import permutations 

N, M = map(int, input().split()) 

p = permutations(range(1, N+1), M) 

for i in p: 
    print(*i)

이건 순열 모듈을 불러온 간편한 풀이 다만 DFS로 순열 만드는 법을 정확히 숙지했을때 위 방법을 사용하자.