[백준] 모든 수열

출처::  www.acmicpc.net/problem/10974

분류:: dfs

 

1. 문제 이해 및 해결과정

1) dfs , 결과배열, 체크배열 따로 두는 경우

2) dfs, 결과배열에 숫자까지 넣어서 

3) permutation 라이브러리 이용

- 속도가 가장 빠르다 

 

2. 풀이방법

1) dfs , 결과배열, 체크배열 따로 두는 경우

#모든 순열
#https://www.acmicpc.net/problem/10974
import sys
sys.stdin = open("input.txt","r")
n=int(input())
ch=[False]*(n+1)
res=[0]*(n)
def dfs(d):
    if d==n:
        print(' '.join(map(str,res)))
    else:
        for i in range(1,n+1):
            if ch[i]==True:
                continue
            res[d]=i #결과배열
            ch[i]=True
            dfs(d+1)
            ch[i]=False #체크해제

dfs(0)

 

2) dfs, 결과배열에 숫자까지 넣어서 

#모든 순열
#https://www.acmicpc.net/problem/10974
import sys
sys.stdin = open("input.txt","r")
n=int(input())
res=[0]*(n)
def dfs(d):
    if d==n:
        print(' '.join(map(str,res)))
    else:
        for i in range(1,n+1):
            if i in res: #res에 i가 이미 있으면  skip
                continue
            res[d]=i #결과배열
            dfs(d+1)
            res[d]=0

dfs(0)

 

3) permutation 라이브러리 이용

#모든 순열
#https://www.acmicpc.net/problem/10974
import sys
from itertools import permutations
sys.stdin = open("input.txt","r")
n=int(input())
arr = [ i for i in range(1,n+1)]
selected=list(permutations(arr,n))
for i in range(len(selected)):
    print(' '.join(map(str,selected[i])))

 

3. 오답원인

 

4. 알게된 점