[알고리즘] 백준 10974 파이썬 - 모든 순열

 

 

10974번: 모든 순열

 

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

 

문제풀이

n= int(input())
s=[]

def dfs():
	#01
    if len(s)==n:
        print(' '.join(map(str,s)))
        return
    #02
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

- 순열 문제지만 dfs 방식으로 풀었다. (dfs 방식은 아래 링크를 참조)

- 기본적으로 재귀를 돌기 때문에 n이 커지면 시간 초과로 인해 사용할 수 없다.

[알고리즘] 백준 2606 파이썬 - 바이러스(DFS 풀이)

 

- n을 입력받는다. 이후 dfs 함수를 정의해준다.

- #01 : 리스트 s의 길이가 n과 같아지면 공백으로 나누어 리스트 s를 출력하고 종료한다.

- #02 : for문을 통해 얻은 i 값이 s에 없으면 추가하고 dfs()함수를 다시 돌고, #01이 만족되면

           다시 돌아와 맨 뒤에 값을 제거한다. 이것을 for문이 끝날 때까지 반복한다.

 

EX) 리스트 s의 변화 : 1-> 1,2 -> 1,2,3(출력) -> s.pop()-> s.pop() -> 1,3 -> 1,3,2(출력) -> .....

최종적으로 위 사진과 같은 결과가 나오게 된다.