DFS 순열, 조합

DFS 순열, 조합

 

python 내장함수를 사용하지 않고 dfs로 순열 조합을 풀 수 있다.

backtracking 개념과 stack 자료구조가 선행되어야 코드를 이해할 수 있다.

이 개념은 N-queen문제를 정리할때 자세히 포스팅 하도록 하겠다.

 

---

 

📄 순열.py

import sys
input = sys.stdin.readline

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

visited = [False]*N
perm = []

def dfs(m):
    if m == 0:
        print(*perm)
        return
    else:
        for i in range(N):
            if visited[i] == False:
                visited[i] = True
                perm.append(i+1)
                dfs(m-1)
                visited[i] = False
                perm.pop()

dfs(M)

---

📄 조합.py

import sys
input = sys.stdin.readline

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

visited = [False]*N
perm = []

# 중복 반문을 피하기 위해 start 파라미터 이용
# start 파라미터는 현재 노드 이후의 노드 중에서
# 탐색할 첫번째 노드의 인덱스 값!!!
# 이미 방문한 노드들을 모두 방문한 후에 
# 현재 노드에서 이후 노드들을 탐색하게 되어 중복 방문을 피할 수 있음

def dfs(m, start):
    if m == 0:
        print(*perm)
        return
    else:
        for i in range(start, N):
            if visited[i] == False:
                visited[i] = True
                perm.append(i+1)
                dfs(m-1, i+1)
                visited[i] = False
                perm.pop()

dfs(M, 0)