[파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 순열 구하기 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index):
    global count
    
    if index == M:
        for i in range(M):
            print(res[i], end=' ')
        print()
        count += 1
        return
    else:
        for i in range(1, N+1):        
            if visited[i] != 1:
                res[index] = i
                visited[i] = 1
                DFS(index+1)
                visited[i] = 0
                
N, M = map(int, input().split())
res = [0] * M
visited = [0] * (N+1)
count = 0
DFS(0)
print(count)

- 저번 '중복순열 구하기' 문제와 다르게 중복이라는 조건이 빠진 문제이다.

- 큰 로직은 저번 문제와 비슷했지만, 같은 숫자를 사용했는지의 여부를 체크하는게 관건이었다.

  → N+1만큼 0으로 초기화된 visited라는 리스트를 선언해주고, DFS 돌면서 사용했으면 1로 체크해준다.

  → 만약 1로 체크되어 있다면 사용 불가능 (X) / 0이면(=1이 아니면) 사용 가능 (O)

  → back 했을 때 사용했던 것을 풀어줘야 하기 때문에, DFS 호출 이후에 다시 0으로 돌려놓아야 한다.