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

풀이

이 문제는 예전에 풀었던 N-queen과 동일한 백트래킹문제이다. 실버3의 낮은 난이도에 속하는데 백트랙킹의 기본 원리를 알면 쉽게 풀수있다.

백트래킹은 DFS와도 비슷한데 다른점이라면 DFS와는 다르게 해당 노드가 유망하지 않으면 취하지 않는다는 것이라는것이다. 이 문제에서 위의 말을 적용하면 만약 앞서 수열에서 이미 선태한 수가 있다면 선택한 수는 제외하고 순회를 한다는 것이다. 그리 어렵지 않은 코드니 보면 쉽게 이해할수있을듯 하다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{

    public static int N;
    public static int M;
    public static int []arr;
    public static boolean []visit;
    public static BufferedWriter br;
    public static StringBuilder sb = new StringBuilder();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visit = new boolean[N];

        DFS(0);
        System.out.println(sb);
    }

    public static void DFS(int deepth){
        if(deepth == M){
            for(int val : arr)
                sb.append(val).append(' ');
            sb.append('\n');
            return;
        }

        for(int i=0; i<N; i++){
            if(visit[i]==false){
                arr[deepth] = i+1;
                visit[i] = true;
                DFS(deepth+1);
                visit[i] = false;
            }
        }
    }
}