[백준] 모든 순열

www.acmicpc.net/problem/10974

문제 해석

n이 입력되었을때
1부터 순회하면서 사전순으로 가능한 모든 순열을 출력하라

문제 풀이

12345를 출력하고 다음 12354를 출력한다고 생각했을때
1234를 선택한 시점에서 4는 선택해봤으니
4를 선택하기 이전으로 돌아가 5를 먼저 선택하는 개념

조건없이 모든 경우를 탐색하는 백트레킹 방법

 

import java.util.*;

public class Main {

    static int[] checked;
    static int N;
    static ArrayList<Integer> list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        checked = new int[N + 1];
        list = new ArrayList<Integer>();

        dfs();

    }

    public static void dfs(){

        if(list.size() == N){
            for(Integer i : list){
                System.out.print(i + " ");
            }System.out.println();
        }

        for(int i = 1 ; i <= N; i++){
            if(checked[i] != 1) {
                checked[i] = 1;
                list.add(i);
                dfs();
                checked[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }
}