[BaekJoon] #15649 N과 M (1)

문제이해

이 문제는 n과 m을 입력받고, 1부터 n까지 자연수 중에서 중복없이 M개를 고른 수열을 출력하는 문제입니다. 이때, 수열은 증가하는 순서로 출력해야 합니다.

문제접근

이 문제는 백트래킹을 이용하는 문제입니다. DFS(Depth First Search)는 기본적으로 모든 경로를 깊이 우선으로 탐색하지만, 백트래킹을 사용해서 탐색의 범위를 제한하고, 조건에 맞지 않는 경로는 중간에 가지치기할 수 있습니다.

모든 노드를 탐색하는 DFS와 유사한데, 차이점은

깊이가 m 이 되었을때, 현재의 arr의 모든 값을 출력하고 탐색을 종료합니다.

또한, DFS에서는 중복해서 탐지하는것을 방지하기 위해 visited[] 배열을 사용합니다.

BackTrack 하기 위해서 방문처리 해주었던 노드를 다시 false값으로 만들어 방문을 풀어주어야 합니다.

이 문제에서는 M개의 수열을 선택하는게 목표이기 때문에 depth = m 이 되는 순간 탐색을 종료하고 배열에 담았던 수열을 출력하면 됩니다.

방문하지 않은 인덱스에 대해 방문처리해주고, 해당 깊이에 해당하는 값을 넣어주고, 그 깊이를 더해 재귀호출해주면 됩니다.

code

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


public class Main {
    static int arr[];
    static boolean visited[];
    static int n,m;
    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());
        visited = new boolean[n];
        arr = new int[m];

        DFS(n,m,0);
        System.out.println(sb);

    }
    static void DFS(int n, int m , int depth ){
            if(depth == m ){
                for(int k : arr){
                    sb.append(k+" ");
                }
                sb.append("\n");
                return;
            }
            for(int i=0; i<n; i++){
                if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1; // 깊이에 해당하는 값을 넣고
                DFS(n, m, depth + 1); // 깊이를 하나 더해 재귀호출 
                visited[i] = false; // backTrack을 위해서 방문처리 해제
            }
            }

    }
}