백준 10974번: 모든 순열 풀이 Python

✅ 백준 10974번: 모든 순열 풀이

🧩 문제 설명

이 문제는 1부터 N까지의 숫자를 가지고 만들 수 있는 모든 순열을 사전순으로 출력하는 문제입니다.

예를 들어 N = 3이라면, 다음과 같은 출력이 나와야 합니다.

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

즉, 숫자들을 조합해서 만들 수 있는 모든 순열을 하나씩 출력하는 프로그램을 만들어야 합니다.

✔ 입력:
정수 N (1 ≤ N ≤ 8)

✔ 출력:
1부터 N까지의 수로 만들 수 있는 모든 순열을 한 줄씩 출력 (총 N!개의 줄)

💡 문제 풀이 아이디어

이 문제를 해결하기 위해 아래와 같은 전략을 세웠습니다:

1. 빈 배열(arr)을 준비해서 여기에 숫자들을 하나씩 채워 넣는다.
2. 배열이 꽉 찼다는 건 곧 하나의 순열이 완성되었다는 뜻이며, 이는 depth == N일 때 알 수 있다.
3. 순열을 만들기 위해 재귀 호출을 이용한다. 즉, 한 숫자를 선택하고 → 다음 숫자를 재귀로 선택 → ... 이런 식으로 전체 조합을 완성해 나간다.
4. 숫자가 중복되지 않도록 하기 위해 used 배열을 사용한다. 이미 선택한 숫자는 다시 고르지 않도록 체크한다.
5. 매 단계마다 1부터 N까지 숫자 중에서 아직 안 쓴 숫자가 있으면 그것을 골라서 사용해보고, 나중에 다시 되돌리는 방식으로 백트래킹을 한다.

🔧 문제 풀이 방법 (Python 코드)

def permu(arr, used, depth, N):
    if depth == N:
        print(*arr)
        return

    for i in range(1, N + 1):
        if not used[i]:
            used[i] = True
            arr[depth] = i
            permu(arr, used, depth + 1, N)
            used[i] = False

N = int(input())
arr = [0] * N
used = [False] * (N + 1)
permu(arr, used, 0, N)

🔍 N = 3, 재귀 호출 흐름 완전 추적

목표:
permu(arr, used, depth, 3) 함수가 어떤 순서로 호출되고, 어디서 출력이 일어나고, 어떤 상태로 돌아오는지를 완전하게 보여드리겠습니다.

전제:

def permu(arr, used, depth, N):
    if depth == N:
        print(*arr)
        return

    for i in range(1, N + 1):
        if not used[i]:
            used[i] = True
            arr[depth] = i
            permu(arr, used, depth + 1, N)
            used[i] = False

🎯 [1단계] depth = 0

for i in range(1, 4):

👉 i = 1

• used[1] = True
• arr[0] = 1
• → permu(1) 호출

🎯 [2단계] depth = 1

for i in range(1, 4):

👉 i = 1

• used[1] == True → 건너뜀

👉 i = 2

• used[2] = True
• arr[1] = 2
• → permu(2) 호출

🎯 [3단계] depth = 2

for i in range(1, 4):

👉 i = 1 → used[1] == True → 건너뜀

👉 i = 2 → used[2] == True → 건너뜀

👉 i = 3

• used[3] = True
• arr[2] = 3
• → permu(3) 호출

✅ [4단계] depth = 3 → 출력 조건 도달

arr = [1, 2, 3]
출력: 1 2 3

→ 복귀 (depth = 2)

🔙 [백트래킹] depth = 2

• used[3] = False
• for 종료 → 복귀

🔙 depth = 1

• used[2] = False
• for 계속

👉 i = 3

• used[3] = True
• arr[1] = 3
• → permu(2) 호출

🎯 depth = 2

👉 i = 1 → used[1] == True → 건너뜀

👉 i = 2

• used[2] = True
• arr[2] = 2
• → permu(3) 호출

✅ 출력

arr = [1, 3, 2]
출력: 1 3 2

→ 복귀 → used[2] = False → for 종료

🔙 depth = 1 → used[3] = False → for 종료

🔙 depth = 0 → used[1] = False → for 계속

👉 i = 2

• used[2] = True
• arr[0] = 2
• → permu(1) 호출

🎯 depth = 1

👉 i = 1

• used[1] = True
• arr[1] = 1
• → permu(2) 호출

🎯 depth = 2

👉 i = 1 → used[1] == True → 건너뜀

👉 i = 2 → used[2] == True → 건너뜀

👉 i = 3

• used[3] = True
• arr[2] = 3
• → permu(3) 호출

✅ 출력

arr = [2, 1, 3]
출력: 2 1 3

→ 복귀 → used[3] = False → 종료

🔙 depth = 1

• used[1] = False

👉 i = 2 → used[2] == True → 건너뜀

👉 i = 3

• used[3] = True
• arr[1] = 3
• → permu(2) 호출

🎯 depth = 2

👉 i = 1

• used[1] = True
• arr[2] = 1
• → permu(3) 호출

✅ 출력

arr = [2, 3, 1]
출력: 2 3 1

→ 복귀 → used[1] = False → for 종료

🔙 depth = 1 → used[3] = False → for 종료

🔙 depth = 0 → used[2] = False → for 계속

👉 i = 3

• used[3] = True
• arr[0] = 3
• → permu(1) 호출

🎯 depth = 1

👉 i = 1

• used[1] = True
• arr[1] = 1
• → permu(2) 호출

🎯 depth = 2

👉 i = 1 → used[1] == True → 건너뜀

👉 i = 2

• used[2] = True
• arr[2] = 2
• → permu(3) 호출

✅ 출력

arr = [3, 1, 2]
출력: 3 1 2

→ 복귀 → used[2] = False

👉 i = 3 → used[3] == True → 건너뜀

🔙 depth = 1

• used[1] = False

👉 i = 2

• used[2] = True
• arr[1] = 2
• → permu(2) 호출

🎯 depth = 2

👉 i = 1

• used[1] = True
• arr[2] = 1
• → permu(3) 호출

✅ 출력

arr = [3, 2, 1]
출력: 3 2 1

→ 복귀 → used[1] = False → 종료

🔙 모든 재귀 종료 → 최종 완료

🎉 최종 정리: 총 6개의 호출 트리 구조

출력 순열	재귀 호출 경로 (i 값 기준)
1 2 3	i=1 → i=2 → i=3
1 3 2	i=1 → i=3 → i=2
2 1 3	i=2 → i=1 → i=3
2 3 1	i=2 → i=3 → i=1
3 1 2	i=3 → i=1 → i=2
3 2 1	i=3 → i=2 → i=1