[Brute Force][DFS][Backtracking] 백준 10974번 : 모든 순열(풀이 여러 개)

[jeongabae]

실버3

[DFS][Backtracking]로 풀거면 #279 15649번 N과 M(1)도 다시보면 좋음

시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 -- | -- | -- | -- | -- | -- 1 초 | 256 MB | 21702 | 13415 | 10089 | 62.552%

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

출처

• 문제를 만든 사람: baekjoon
• 문제의 오타를 찾은 사람: corea

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

제출한 코드

291 10972번 다음 순열 알고리즘 이용해서 다음다음순열~~~계속 구해서 모든 순열을 다 구했다.

import sys

def next_permutations(a): #다음 순열 구하는 함수
    # 1. a[i-1] < a[i]를 만족하는 가장 큰 i를 찾는다.
    i = n - 1
    while (a[i - 1] >= a[i] and i > 0):  # a[i-1] < a[i]를 만족하지 않는 경우 즉,a[i-1]>=a[i] 그리고 i<0이면 그 전 인덱스 확인.
        i -= 1

    # i<=0이 되면 다 내림차순이란 소리..!(즉 맨 마지막 순열)
    if i <= 0:
        return -1

    # 2. i<=j이면서 a[i-1]<a[j]를 만족하는 가장 큰 j를 찾는다.
    else:
        j = n - 1
        while (a[i - 1] >= a[j]):
            j -= 1

        # 3. a[i-1]과 a[j]를 swap한다.(바꿔준다.)
        a[i - 1], a[j] = a[j], a[i - 1]

        # 4. i번째의 값부터 그 이후 값 모두를 오름차순 정렬
        sort_from_jth_of_a = a[i:]
        sort_from_jth_of_a.sort()
        ans = a[:i] + sort_from_jth_of_a

        # 출력
        print(*ans)
        return ans

n=int(sys.stdin.readline().rstrip())
a=[i for i in range(1,n+1)]
print(*a)
while 1:
    a = next_permutations(a)

    if a==-1:
        break

1등 풀이 : itertools의 permutations함수 이용한게 젤 빠름

다음 순열 풀이 이용해서 나는 풀었지만 시간 여유가 되니까

from itertools import permutations
import sys
print=sys.stdout.write
def BOJ10974():
    n = int(input())
    for i in map(" ".join,permutations([str(i) for i in range(1,n+1)])):
        print(i+"\n")
BOJ10974()

from itertools import permutations #순열 함수

N = int(input())
N_list = [i for i in range(1, N+1)]

for numbers in list(permutations(N_list)):
    for num in numbers:
        print(num, end=' ')
    print()

다른 사람 풀이 : dfs를 이용한 백트래킹

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

def dfs():
    if len(temp) == n:
        print(*temp)
        return
    for i in range(1, n + 1):
        if i not in temp:
            temp.append(i)
            dfs()
            temp.pop()

dfs()