(15649) N과 M(1)

문제

문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

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

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

---

문제 풀이

해당 문제는 백트래킹 알고리즘으로 해결 할 수 있는 문제이다. 입력 되는 n 값 까지의 값을 담을 수 있는 길이가 n 인 배열를 만들고 방문여부를 확인 할 수 있는 visited boolean 배열도 같이 선언한다.

arr = new int[n];
visited = new boolean[n];

그리고 dfs함수를 호출 할 때는 n, m, depth 값을 매개변수로 넘겨주는데 초기 depth 값은 0으로 입력한다.  

solution(n, m, 0);

그렇게 dfs 함수를 수행하게 되면 depth가 m 과 같아지면 출력하는 if문을 거치게 되고, 

if (depth == m) {
    for (int i = 0; i < m; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

그렇지 않을 경우, visited 여부에 따라 arr값을 초기화 시켜주는 반복문을 거치게 된다. 반복문에서는 방문을 하지 않았을 경우, if문을 수행하게 되고 방문 여부를 체크를 하고 arr[depth]를 초기화 해준다.

for (int i = 0; i < n; i++) {
    if (!visited[i]){
        visited[i] = true;
        arr[depth] = i + 1;
        solution(n, m, depth + 1);
        visited[i] = false;
    }
}

해당 if을 나올 때는 다시 방문여부를 false로 변경한다. 

---

나의 답안

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        visited = new boolean[n];

        solution(n, m, 0);
    }

    private static void solution(int n, int m, int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]){
                visited[i] = true;
                arr[depth] = i + 1;
                solution(n, m, depth + 1);
                visited[i] = false;
            }
        }
    }
}