[백준] 15649번 : N과 M (1) - JAVA [자바]

https://www.acmicpc.net/problem/15649

기초적인 DFS 알고리즘 문제이다.

1. M 개를 고른다는 것은 깊이가 M인 그래프를 탐색한다고 생각하면 된다.
2. 중복이 있으면 안되므로 visited 배열을 사용해서 방문 여부를 판별하여 방문했으면 건너뛴다.

DFS 종료 조건 : 깊이가 M이 되면 정답을 추가한다.

dfs 알고리즘

N 까지의 수를 0부터 반복하며 방문했는지 확인한다.

i 번째 수일 때, 방문한적이 없으면 방문을 하고(visited[i] = true) 방문한 수를 배열에 깊이의 위치에 넣는다(numArr[depth] = i+1).
그 후 dfs로 다음 깊이의 노드를 탐색한다.
이를 반복하며 깊이가 M이 됐을때 (M개의 수를 골랐을 때) 고른 수를 정답에 추가하고 다시 전의 깊이로 돌아가서 방금 방문했던 수를 방문 초기화 해주고 다음 수로 넘어간다.

public class bj15649 {

    public static int[] numArr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        visited = new boolean[N];
        numArr = new int[M];

        dfs(0, N, M);

        bw.write(sb + "");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int n, int m) {
        if (depth == m) {
            for (int num : numArr) {
                sb.append(num).append(' ');
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                numArr[depth] = i + 1;
                dfs(depth + 1, n, m);
                visited[i] = false;
            }
        }
    }
}