[백준] N과M(1) (JAVA)

순열(Permutation)을 사용하는 문제

문제를 보자마자 순열을 사용해야겠다고 생각이 들었지만 순열을 어떻게 구현하는지 몰라서 막막했다. 결국 구글링의 도움을 받아 해결했다.

순열은 n개 중에 r개를 중복없이 뽑아(조합:Combination) 나열하는 것이다.
나열하는 것이기 때문에 순서가 중요하다.[1,2,3]과 [2,3,1]은 다르다.

순열은 DFS로 구현할 수 있다.

• arr[] : 1부터 n까지의 숫자가 들어있는 배열
• output[] : 순열의 결과를 저장하는 배열
• visited[] : 이미 방문한 숫자인지 확인하기 위한 배열(중복을 방지하기 위해)
• depth : DFS를 위한 깊이 변수

import java.io.*;

public class No15649_N과M_1 {
    static int arr[];
    static int output[];
    static boolean visited[] ;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String temp[] = br.readLine().split(" ");
        int N = Integer.parseInt(temp[0]);
        int M = Integer.parseInt(temp[1]);

        arr= new int[N];
        output = new int[N];
        visited = new boolean[N];
        for (int i=1;i<=N;i++)
            arr[i-1]=i;


        permutation(0,N,M);
    }

    static void permutation (int depth, int n, int r) {
        if (depth==r){
            for(int i =0 ; i < r; i++) {
                System.out.print(output[i]+" ");
            }
            System.out.println();
            return;
        }

        for (int i=0;i<n;i++) {
            if (!visited[i]) {
                visited[i]=true;
                output[depth] = arr[i];
                permutation(depth+1,n,r);
                visited[i]=false;

            }
        }
    }

}

자바는 순열 라이브러리가 없기 때문에 직접 구현해야한다. 복습을 열심히 해서 안 까먹게 해야겠다.

참고 블로그