[백준 10974번] 모든 순열 - JAVA

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

10974번: 모든 순열

풀이

사용한 알고리즘 : DFS로 구현한 순열(Permutation)

 

풀이전략

순열을 사용하여 주어진 원소들 중 가질 수 있는 모든 경우의 수를 찾는다.

 

이를 그림으로 나타내면 아래와 같다.

DFS를 사용해 완전 탐색을 수행하여 위와 같은 구조를 구현한다.

 

위 그림에서 맨 윗 노드를 0 계층이라고 하면, 맨 아래 노드는 3 계층(Layer)이다.

 

코드에서 L은 현재 탐색중인 노드의 계층을, R은 최하단의 계층을 뜻하는데

종료조건은 L==R 로, 현재 탐색 중인 노드의 계층이 최하단의 계층이면 DFS 탐색을 종료하도록 하였다.

 

다만 L==R이 아닌 경우에는 완전 탐색하되, 

해당 노드를 이전 계층에서 이미 탐색한 상태면 다시 방문하지 않도록 check 배열을 사용했다.

 

아래 제출코드에서

check[i]=true;
dfs(L+1);
check[i]=false;

위 부분이 이해하기 어려울 수 있다.

이는 방문했었던 노드를 다시 방문하지 않도록 하기 위해 사용한 배열로

dfs 메소드를 통해 재귀하기 전에는 재귀한 함수에서 해당 노드를 다시 방문하지 않도록 방문처리하였다가,

dfs 메소드를 탈출하고 나서는, 완전 탐색을 위해 해당 노드를 다시 방문할 수 있도록 방문 미처리한 것이다.

 

제출코드

import java.io.*;

public class Main {
    static boolean check[];
    static int result[];
    static int R;
    static void dfs(int L){
        if(L==R){
            for(int i=0;i<R;++i){
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
        else{
            for(int i=0;i<R;++i){
                if(!check[i]){
                    result[L]=i+1;
                    check[i]=true;
                    dfs(L+1);
                    check[i]=false;
                }
            }
        }
    }

    public static void main(String agrs[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        R=N;

        check=new boolean[N+1];
        result=new int[N+1];

        dfs(0);
    }
}