[백준] 15650번 N과 M (2) java

1. 백준 15650번 문제

1. 문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

2. 입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

3. 출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

2. 문제 해석

중복을 허용 안하고 조합할 수 있는 수로 '비내림차순'인 수열을 출력하는 문제입니다.

3. 문제 풀이

import java.util.Scanner;

public class Main {

    public static int N, M;
    public static int[] arr;
    public static boolean[] visit;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        N = in.nextInt(); //자연수 입력받기
        M = in.nextInt(); //깊이 입력받기
        arr = new int[M]; //깊이 만큼 배열 생성
        visit = new boolean[N];//자연수가 중복되지않게 방문 표시를 해준다.

        dfs(1, 0);
    }
    public static void dfs(int at, int depth) {
        //phase1
        if (depth == M) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }
        //phase2
        for (int i = at; i <= N; i++) {
            if(visit[i-1] != true) { //자연수의 갯수만큼 배열이 존재한다.
                visit[i-1] = true; //visit[0] = true가 됨으로 i가 1일경우는 다음 dfs(i, depth + 1);에 대입될 수 없다.
                arr[depth] = i; //처음자리에는 1 이 들어가고, 다음 자리에 1이 들어올 수 없으므로 2,3,4 가 들어간다.
                                //각각 phase1의 조건에 충족이 되면 출력이 된다.
                dfs(i, depth + 1);
                visit[i-1] = false; //이 false가 없으면 1 2 /1 3 /1 4 가 출력 된 뒤로 2,3,4가 true로 묶이기 때문에 
                //1 2/ 1 3 /1 4만 출력이 되고 끝난다.
            }
        }
    }
}

출력 결과

4
2
1 2 
1 3 
1 4 
2 3 
2 4 
3 4