파이썬 알고리즘 049 | 순열 구하기 (DFS)

### 49. 순열 구하기
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(x):
    global cnt
    global res
    if x==m:
        for i in range(m):
            if res[0]!=res[1]:  
                cnt+=1
                print(res[i], end=' ')
        print()
        return()
    else : 
        for i in range(1,n+1):
            res[x]=i
            DFS(x+1)

if __name__=='__main__' :
    n, m = map(int, input().split())
    res=[0]*(m)
    cnt=0
    DFS(0)
    print(int(cnt/2))
    

• +a[0]!=a[1] 라고 하면 세개를 뽑으라고 하면 155, 211 같은 애들은 못 거른다
  =====> if len(res)==len(set(res)) 이렇게 해주면 된다
  ================>그럼에도 공백 프라블럼 있다. 밑과 같은 사진처럼 결과가 나옴
  

def DFS(x):
    global cnt
    global res
    if x==m:
        for i in range(1,m+1):
            if len(res)==len(set(res)):
                cnt+=1
                print(res[i], end=' ')
        print()
        return()
    else : 
        for i in range(1,n+1):
            res[x+1]=i
            DFS(x+1)

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

=> 풀이를 듣고 풀어봤는데 ch가 가득1로 채워져서 실패..이걸 초기화해야한다, 근데 초기화하는 방법을 모르겠다

def DFS(x):
    global cnt
    global res
    if x==m:
        for i in range(1,m+1):
                cnt+=1
                print(res[i], end=' ')
        print()
        return()
    else : 
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1 #이렇게 되면 초반에 ch가 모두 1로 차버려서 빨리 끝나버림, 근데 초기화하는 방법을 모르겠음
                res[x+1]=i
                DFS(x+1)

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

<풀이>

-DFS(x)에 해당하는 x자리에다가 for반복문으로 생성된 i(1,2,3..)들을 넣는 건데,
강사님은 추가적으로 ch생성해서 체크하는 걸 만들어서, ch[i] 에다가 ch자리에 아무도 없으면 (==0이라면) 1을 넣고 아니라면 가지를 끊어버리는 걸로...
아

def DFS(x):
    global cnt
    global res
    if x==m:
        for i in range(1,m+1):
                cnt+=1
                print(res[i], end=' ')
        print()
        return()
    else : 
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[x+1]=i
                DFS(x+1)
                ch[i]=0 #******이 부분은 dfs호출되고, 다른 가지로 향할 때

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

<반성점>

• ch라는 체크리스트를 만들어서 걸러줄 생각을 하지 못했었다
• DFS를 부르고 ch=0이라고 초기화 하면
  D(1) 밑 D(2) 가지들이 1, 2, 3, 있다고 하면 1에서 ch=1해주고, 다시 D(1)올라가서 2랑 비교할 때 1에서 체크된것은 사라진다
• 이 ch방법 잘 기억해두자

<배운 점>

• 리스트안에 중복 있는지 체크 방법
  : if len(res)==len(set(res)) (근데 문제에서 이거 쓰이면 공백들이 투머치하게 나와서 여기서는 적합하지 않은 방법)

<2회독 내 풀이>

def DFS(x) :
    global cnt
    if x==m:
        for i in res:
            print(i, end=' ')
        cnt+=1
        print()
    else : 
        for i in range(1,n+1):
            if ch[i]==0:
                ch[i]=1
                res[x]=i
                DFS(x+1)
                ch[i]=0
if __name__=='__main__' :
    n, m = map(int, input().split())
    res=[0]*m
    ch=[0]*(n+1)
    cnt=0
    DFS(0)
    print(cnt)