백준 10974 순열

백준 10974 순열

1. 문제 링크

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

 

2. 문제 해결에 대한 아이디어

1. 문제의 테스트 케이스는 [1, 2, 3]에 대한 순열의 결과이다.
2. visit 을 사용하여, 순열 결과 배열(int[] candidate)에 들어가는 숫자의 순서를 제어한다.
3. 백트래킹으로 모든 순열을 구할 수 있으며, 테스트 케이스 기준으로 아래와 같이 동작한다. (depth를 인데스로 사용하고 있다.)
4. 재귀의 depth별 결과는 아래와 같다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[] candidate; // 순열의 결과가 담길 배열
    static int[] nums;
    static boolean[] visit;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        nums = new int[N];
        visit = new boolean[N];
        candidate = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = i + 1;
        }

        permutation(0);
    }

    static void permutation(int depth) {
        if (depth == N) {
            Arrays.stream(candidate).forEach(v -> System.out.print(v + " "));
            System.out.println();
            return;
        }

        // 항상 0부터 시작하여 visit[i]를 체크
        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                // depth 를 인덱스로 사용하는 것을 잊지말자
                candidate[depth] = nums[i];
                permutation(depth + 1);
                visit[i] = false;
            }
        }
    }
}

4. 채점 결과

5. 느낀 점

1. 순열의 전형적인 문제였으며, 익숙해져야하는 유형이다.
2. 재귀를 들어갔다 나오면서 visit 배열을 원래 상태로 만들어야한다.
3. 순열 외에 중복순열, 중복조합, 조합 등의 문제는 위의 permutation 함수 코드를 응용해서 풀면 된다.