[BOJ/Java] 모든 순열 (10974)

모든 순열 (10974)

1. 문제 분석

문제 개요

주어진 자연수 N에 대해, 1부터 N까지의 모든 숫자로 이루어진 순열을 사전순으로 출력하는 문제이다.

입력 형식

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

출력 형식

모든 순열을 사전순으로 출력한다. 각 순열은 한 줄에 하나씩 출력한다.

2. 알고리즘 종류

이 문제는 백트래킹(Backtracking) 알고리즘을 사용하여 해결한다. 백트래킹을 통해 가능한 모든 숫자 조합을 생성하고, 이미 선택된 숫자는 다시 선택하지 않도록 하여 모든 순열을 출력한다.

3. 주요 부분 및 코드 작성 방법

1. 백트래킹을 사용한 순열 생성

• 백트래킹 기법을 사용하여 가능한 모든 숫자 조합을 생성한다. perm 함수가 재귀적으로 호출되며, 각 호출마다 다음 숫자를 선택하여 배열에 추가한다.

2. 숫자 선택 여부 체크

• isSelected 배열을 통해 이미 선택된 숫자는 중복하여 선택되지 않도록 관리한다.

3. 재귀 함수 종료 조건

• 재귀 함수 perm은 cnt가 N과 같아질 때까지 호출된다. 이 경우 모든 숫자가 선택된 것이므로 현재까지의 순열을 출력한다.

4. 코드 설명

(1) 메인 함수 main

• 입력 처리
  • 첫 번째 줄에서 자연수 N을 입력받는다.
  • number 배열은 현재 생성 중인 순열을 저장한다.
  • isSelected 배열은 숫자가 선택되었는지를 체크하기 위한 배열이다.
  • perm(0)을 호출하여 백트래킹 알고리즘을 시작한다.
• N = Integer.parseInt(br.readLine()); number = new int[N]; isSelected = new boolean[N + 1]; perm(0);
• 순열 생성 함수 호출
  • perm 함수를 호출하여 0부터 시작하는 모든 순열을 생성한다.
• perm(0);

(2) 백트래킹 함수 perm

• 재귀 함수 호출
  • cnt가 N과 같아지면, 현재까지 생성된 순열을 출력한다.
• if (cnt == N) { for (int i : number) System.out.print(i + " "); System.out.println(); }
• 숫자 선택 및 백트래킹 진행
  • 1부터 N까지의 숫자 중 선택되지 않은 숫자를 순차적으로 선택한다.
  • number[cnt]에 선택한 숫자를 저장하고, isSelected[i]를 true로 설정하여 선택 상태를 기록한다.
  • 재귀 호출을 통해 다음 숫자를 선택한다.
  • 재귀 호출이 종료된 후에는 isSelected[i]를 false로 설정하여 다음 반복에서 다른 숫자를 선택할 수 있도록 한다.
• for (int i = 1; i <= N; i++) { if (isSelected[i]) continue; number[cnt] = i; isSelected[i] = true; perm(cnt + 1); isSelected[i] = false; }

5. 전체 코드

import java.io.*;
import java.util.Arrays;

public class BOJ10974 {
    static int N; // 주어진 자연수 N
    static int[] number; // 현재 순열을 저장하는 배열
    static boolean[] isSelected; // 숫자 선택 여부를 체크하는 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 처리
        N = Integer.parseInt(br.readLine());
        number = new int[N]; // 순열을 저장할 배열 초기화
        isSelected = new boolean[N + 1]; // 숫자 선택 여부를 확인할 배열 초기화

        // 백트래킹 알고리즘을 사용하여 순열 생성
        perm(0); // 순열 생성 시작
    }

    // 백트래킹을 사용한 순열 생성 함수
    public static void perm(int cnt) {
        if (cnt == N) { // 모든 숫자가 선택되었을 때
            for (int i : number) System.out.print(i + " "); // 현재 순열 출력
            System.out.println(); // 줄바꿈
        }
        else {
            for (int i = 1; i <= N; i++) { // 1부터 N까지의 숫자를 순차적으로 선택
                if (isSelected[i]) continue; // 이미 선택된 숫자는 건너뜀
                number[cnt] = i; // 선택한 숫자를 현재 순열에 저장
                isSelected[i] = true; // 선택 상태 기록
                perm(cnt + 1); // 다음 숫자 선택을 위해 재귀 호출
                isSelected[i] = false; // 선택 상태 초기화 (백트래킹)
            }
        }
    }
}