백준 10974번: 모든 순열 풀이 C++

✅ 백준 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까지 숫자 중에서 아직 안 쓴 숫자가 있으면 그것을 골라서 사용해보고, 나중에 다시 되돌리는 방식으로 백트래킹을 한다.

🔧 문제 풀이 방법 (C++ 코드)

#include <iostream>
using namespace std;

// 순열을 재귀적으로 생성하는 함수
void permu(int* arr, int* used, int depth, int N)
{
	if (depth == N)  // 배열이 가득 찼다면 출력
	{
		for (int i = 0; i < N; i++)
			cout << arr[i] << " ";
		cout << endl;
		return;
	}

	// 1부터 N까지 숫자 중에서
	for (int i = 1; i <= N; i++)
	{
		if (!used[i])  // 아직 사용하지 않은 숫자라면
		{
			used[i] = 1;      // 사용 표시
			arr[depth] = i;   // 현재 위치에 저장
			permu(arr, used, depth + 1, N);  // 다음 단계로 이동
			used[i] = 0;      // 백트래킹 (원상복구)
		}
	}
}

int main(void)
{
	int N;
	cin >> N;

	int* arr = new int[N];          // 결과 순열을 담을 배열
	int* used = new int[N + 1]{0};  // 숫자 사용 여부 확인 배열

	permu(arr, used, 0, N);         // 순열 생성 시작

	delete[] arr;
	delete[] used;
	return 0;
}

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

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

전제:

void permu(int* arr, int* used, int depth, int N) {
    if (depth == N) {
        // 출력
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (!used[i]) {
            used[i] = 1;
            arr[depth] = i;
            permu(arr, used, depth + 1, N);
            used[i] = 0; // 백트래킹
        }
    }
}

🎯 [1단계] depth = 0

for (i = 1; i <= 3; i++)

👉 i = 1

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

🎯 [2단계] depth = 1

for (i = 1; i <= 3; i++)

👉 i = 1

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

👉 i = 2

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

🎯 [3단계] depth = 2

for (i = 1; i <= 3; i++)

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

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

👉 i = 3

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

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

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

→ 복귀 (depth 2로)

🔙 [백트래킹] depth = 2 (i = 3 끝)

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

🔙 depth = 1 (i = 2 끝)

• used[2] = 0
• for 계속

👉 i = 3

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

🎯 depth = 2

for (i = 1; i <= 3; i++)

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

👉 i = 2

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

✅ depth = 3

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

→ 복귀 (depth = 2)

🔙 depth = 2

• used[2] = 0
• for 계속

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

→ for 종료 → 복귀

🔙 depth = 1

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

🔙 depth = 0

• used[1] = 0
• for 계속

👉 i = 2

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

🎯 depth = 1

for (i = 1; i <= 3; i++)

👉 i = 1

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

🎯 depth = 2

for (i = 1; i <= 3; i++)

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

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

👉 i = 3

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

✅ depth = 3

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

→ 복귀

🔙 depth = 2 → used[3] = 0 → for 종료

→ 복귀
depth = 1 → used[1] = 0

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

👉 i = 3

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

🎯 depth = 2

👉 i = 1

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

✅ 출력

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

→ 복귀 → used[1] = 0
→ depth = 2, i = 2 → used[2] == 1 → 건너뜀
→ i = 3 → used[3] == 1 → 건너뜀
→ 종료 → 복귀

🔙 depth = 1 → used[3] = 0

→ 종료 → 복귀
→ depth = 0 → used[2] = 0

👉 i = 3

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

🎯 depth = 1

👉 i = 1

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

🎯 depth = 2

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

👉 i = 2

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

✅ 출력

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

→ 복귀 → used[2] = 0 → i = 3 → used[3] == 1 → 건너뜀
→ 복귀 → used[1] = 0

👉 i = 2

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

🎯 depth = 2

👉 i = 1

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

✅ 출력

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

→ 복귀 → used[1] = 0
→ i = 2 → used[2] == 1
→ i = 3 → used[3] == 1
→ 복귀 → used[2] = 0

🎉 최종 정리: 총 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