백준 15649 N과M(1) - DFS

N개중 중복없이 M개를 추출하는 조합문제이다.

순열조합 정도는 묶어서 DFS 풀이해야된다고 기억하는 것도 괜찮고, 다시 생각해보면 1부터 N까지 가면서 M개를 선택하는 "경로 를 선택"히는 문제이므로 DFS라고 생각할 수 있다.

코드를 만들어가는 과정

그 다음 생각할만한건 M개를 선택해야하니까 결국 depth 즉, 몇개가 담겨있는지 정보가 필요하겠구나.

그러면 limit도 지정해줘야하구나

void dfs(int limit, int depth){
  if(limit == depth){
  // 출력 및 리턴
  }

출력하기 위해서 기존 배열을 저장하면서 와야구나 -> int[] value 변수 추가

void dfs(int limit, int depth, int[] value) {

        // 종료조건
        if (limit==depth){
            // value 출력
            for (int i = 0; i < limit; i++) {
                // limit 개
                System.out.print(String.valueOf(value[i+1])+" ");
            }
            System.out.println();
            return ;
        }

이렇게하니 중복된 변수를 걸러야하는데, 여기서 visited[] 배열을 통해 사용된 변수를 체크하면 된다.

    private static void dfs(int limit, int depth, boolean[] visited, int[] value) {

        // 종료조건
        if (limit==depth){
            // value 출력
            for (int i = 0; i < limit; i++) {
                // limit 개
                System.out.print(String.valueOf(value[i+1])+" ");
            }
            System.out.println();
            return ;
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]){
                // value[depth]  : 기존값
                value[depth+1]= i;
                visited[i]=true;
                dfs(limit,depth+1,visited,value);
            }
        }

이렇게 방문에만 체크하면 dfs 하기전후 상태값이 바뀌므로 DFS가 끝난후 visited[]를 false로 변경해주는 코드도 추가하자

최종

import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;

    public static void main(String[] args) throws IOException {

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



        boolean[] visited = new boolean[N + 1];

        dfs(M,0,visited, new int[N+1]); // 현재 idx
    }

    private static void dfs(int limit, int depth, boolean[] visited, int[] value) {

        // 종료조건
        if (limit==depth){
            // value 출력
            for (int i = 0; i < limit; i++) {
                // limit 개
                System.out.print(String.valueOf(value[i+1])+" ");
            }
            System.out.println();
            return ;
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]){
                // value[depth]  : 기존값
                value[depth+1]= i;
                visited[i]=true;
                dfs(limit,depth+1,visited,value);
                visited[i]=false;
            }
        }
    }
}