BOJ 15649) N과 M(1)

문제

 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

해결

 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른다고 했으니, dfs를 이용한 백트래킹으로 구현하면 되겠다고 생각이 들었다.

 

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        // 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열.
        int N = sc.nextInt();
        int M = sc.nextInt();

        boolean[] isVisited = new boolean[N+1];
        int[] arr = new int[M+1];

        for(int i=0; i<N+1; i++)
            isVisited[i] = false;

        dfs(isVisited, arr, N, M, 0);

    }

    private static void dfs(boolean[] isVisited, int[] arr, int N, int M, int depth) {

        if(depth==M) {
            for (int i=1; i<M+1; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
            return;
        }

        for(int i=1; i<=N; i++) {
            if(!isVisited[i]) { //유망성 판단, dfs
                isVisited[i]=true;
                arr[depth+1] = i;
                dfs(isVisited, arr, N, M, depth + 1);
                isVisited[i]=false;
            }
        }

    }
}

유망성을 판단할 기준이 방문 여부이므로, 방문 여부를 체크하여 유망한지 여부를 판단한다. 만약 유망한지 여부를 판단하지 않는다면 브루트포스를 이용한 탐색과 다를 바 없게 된다. 또한 이 문제에서는 브루트포스만을 이용한 탐색 방법이 훨씬 생각하기도 복잡할 것 같다.