파이썬 알고리즘-50 (DFS/BFS) 순열 구하기

jiffydev·2020년 9월 22일
0

Algorithm

목록 보기
57/134
post-thumbnail

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

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

▣ 입력예제 1
3 2

▣ 출력예제 1
1 2
1 3
2 1
2 3
3 1
3 2
6

내 코드

def dfs(v):
    global cnt
    if v==m:
        cnt+=1
        for i in res:
            print(i, end=' ')
        print()
    else:
        for i in range(1,n+1):
            if ch[i]==0:
                res[v]=i
                ch[i]=1
                dfs(v+1)
                ch[i]=0

n,m=map(int, input().split())
res=[0]*m
ch=[0]*(n+1)
cnt=0
dfs(0)
print(cnt)

풀이와 거의 동일하게 풀었다.

풀이

def DFS(L):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                DFS(L+1)
                ch[i]=0

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*n
    ch=[0]*(n+1)
    cnt=0
    DFS(0)
    print(cnt)

반성점

배운 것

profile
잘 & 열심히 살고싶은 개발자

0개의 댓글