[백준15649] N과 M(1) / Java

링크 | https://www.acmicpc.net/problem/15649

문제 |

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력 |

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

출력 |

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

예제 |

입력

4 4

출력

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

Solution |

1부터 N까지의 자연수 중에서 중복없이 M를 고른 수열 = 순열 nPm

• boolean list visted에서 false인 값들만 이용하고, 이용한 값들은 true로 바꾸어 중복을 방지한다.
• DFS를 이용하여 순열 값을 순서대로 출력한다.

import java.util.Scanner;

public class NandM_1 {
	public static void main(String[] args) {
        int N=0, M =0;
        Scanner input = new Scanner(System.in);
        
        N = input.nextInt();
        M = input.nextInt();
        input.close();
        
        if (1>M || 1>N || M>8 || N>8 || M>N) {
        	System.out.println("올바른 입력값이 아닙니다.");
        	return;
        }
        int[] arr = new int[N];
        int[] output = new int[N];
        boolean[] visited = new boolean[N];
        
        makearray(arr, N);
        permutation(arr, output, visited, 0, N, M);
        System.out.println();
        

    }

	static void makearray(int[] arr, int n) {
        for(int i=0; i<n; i++) {
        	arr[i] = i+1;
        }     
	}

    static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int m) {
        if (depth == m) { // depth끝까지 다다르면 output 출력
            print(output, m);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] == false) { // 중복 방지
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth + 1, n, m);
                visited[i] = false;
            }
        }
    }

    // 배열 출력
    static void print(int[] arr, int r) {
        for (int i = 0; i < r; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}