[Python-CodingTest] 6-8. 🌟 순열 구하기 (DFS: 깊이우선탐색)

순열 구하기

문제 정리

입력

3 2

처리 과정

1. 중복을 허락하지 않는 체크리스트(=ch) 생성 (인덱스 번호가 동일하도록 n+1개 생성)
2. 순열 결과 리스트(=res[L])에 값 넣기 전에, 체크리스트의 값이 0인지 확인
3. 체크리스트 값이 0 이라면, 1을 집어넣고 순열 결과 리스트(=res[L])에 값 넣기
4. DFS(L+1)로 재귀
5. 재귀 후에 back을 한 뒤에는, 체크리스트를 0으로 되돌리기
6. L이 m(=2)이 되면 res 출력
7. 총 개수를 카운트하기 위한 global 변수 cnt

출력

1 2 
1 3 
2 1 
2 3 
3 1 
3 2 
6

내 답

import sys
sys.stdin = open("./input/in8.txt", "rt")

def DFS(L):
    global cnt
    global ch
    if L==m:
        for x in res:
            print(x,end=' ')
        print()
        cnt+=1
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                res[L]=i
                ch[i]=1
                DFS(L+1)
        ch=[0 for _ in range(n+1)] # ch를 0으로 초기화

if __name__=="__main__":
    n,m=map(int,input().split())

    res=[0]*m
    cnt=0
    ch=[0]*(n+1) # 중복을 허락하지 않는 체크리스트 (인덱스 번호와 동일)

    DFS(0)
    print(cnt)

풀이

import sys
sys.stdin = open("./input/in8.txt", "rt")

def DFS(L):
    global cnt
    if L==m:
        for x in res:
            print(x, end=' ')
        print()
        cnt+=1
    else:
        for i in range(1,n+1):
            if ch[i]==0: # 체크리스트의 값이 0일때만 순열(=res) 만들기
                ch[i]=1
                res[L]=i
                
                DFS(L+1)
                ch[i]=0 # 🌟 back을 한 뒤에는 체크리스트 되돌리기

if __name__=="__main__":
    n,m=map(int,input().split())

    res=[0]*m
    cnt=0
    ch=[0]*(n+1) # 🌟 중복을 허락하지 않는 체크리스트 (인덱스 번호와 동일)

    DFS(0)
    print(cnt)

정리

• 순열 -> 중복을 허락하지 않는 체크리스트(=ch) 만들기!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기