[백준]15649번 N과 M(1)(JAVA)

0. 문제 링크

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

15649번: N과 M (1)

 

1. 문제 설명

1) 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 구하기 -> 순열

 

2. 입출력

// input
4 2

// output
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

3. 코드

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

public class b15649 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 1. 입력
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 2. N개 중에 중복 없이 M개 고르기
		int[] arr = new int[N]; // 원본 배열 
		boolean[] v = new boolean[N]; // 방문 배열
		int[] sel = new int[M]; // 선택 배열
		
		for(int n = 0; n < N; n++) { // 원본 배열 생성
			arr[n] = n+1;
		}
		
		recursive(arr, sel, v, 0, 0);
	}
	
	// arr : 원본 배열, sel : 선택 배열, idx : 원본 배열 인덱스, k : 선택 배열 인덱스
	private static void recursive(int[] arr, int[] sel, boolean[] v, int idx, int k) {
		// basis part
		if(k == sel.length) { // M개 골랐으면 출력
			for(int s = 0; s < sel.length; s++) {
				System.out.print(sel[s] + " ");
			}
			System.out.println();
			return;
		}
		
		// inductive part
		for(int i = 0; i < arr.length; i++) {
			if(v[i] == false) { // 미방문 인덱스에 대해서 
				sel[k] = arr[i]; // 하나 선택하기
				v[i] = true; // 방문 처리
				recursive(arr, sel, v, idx+1, k+1);
				v[i] = false; // 방문 처리 해제
			}
		}
	}
}

 

실행 결과

 

4. 회고

1) 순열 재귀로 구현

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b15649.java