순열 구하기 (DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Wa5t

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

내 풀이

#내 풀이       //답은 맞음
def DFS(L):
    global res, cnt
    if L == m:
        if len(res) != len(set(res)):
            pass
        else:
            for i in res:
                print(i, end = ' ')
            print()
            cnt += 1
    else:
        for i in range(1, n+1):
            res[L] = i
            DFS(L+1)

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

다른 부분은 강사님과 동일한데

나는 중복순열을 모두 구한 다음에

set 함수 기능을 이용하여 원소중에 같은 숫자가 있으면

제외하는 방식으로 순열을 만들어봤다

 

강의 풀이

#강의 풀이
def DFS(L):
    global res, cnt
    if L == m:
        for j in range(L):
            print(res[j], 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] * m
    ch = [0] * (n+1)
    cnt = 0
    DFS(0)
    print(cnt)

강사님은 그 숫자가 쓰였는지 안쓰였는지 검사하는 ch 배열을 만들어

처음 DFS 를 순환할때 ch 값을 1로 설정하고

순열에 i를 추가한다음 

그 아래 DFS가 맨 끝에 닫을땐 return 하기전에 다시 ch 값을 0으로 풀어주었다.