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

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

15649번: N과 M (1)

백준 15649번 N과 M(1) 문제 링크입니다.

 

핵심

이 문제는 백트래킹을 사용하여서 풀어야 한다. 재귀 호출을 통해 푸는 방식이다.

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹 - 나무위키

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	public static int[] arr;
	public static boolean[] check;
	public static StringBuilder sb = new StringBuilder();
	
	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[M];
		check = new boolean[N];
		rec(M,N,0);	
		System.out.println(sb);
	}	
	public static void rec(int M, int N, int index) {
		if(M==index) {
			for(int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
		for(int i=0; i <N;i++) {
			if(!check[i]) {
				check[i]=true;
				arr[index]=i+1;
				rec(M, N, index + 1);
				check[i]=false;
			}
		}
	}
}

해설

처음에는 숫자의 범위가 들어오고, 그 뒤 순열의 수를 받는다.

재귀 함수 rec 호출하는데, 처음 index값을 0으로 호출한다.

check는 이미 사용된 수인지 확인하기 위해 사용된다.

사용된 수가 아니라면, check를 사용했으므로 바꾸고, arr에 값을 추가한다.

이후 index값을 1 더한 자기 자신을 호출한다.

만약 M==index가 되면 배열을 sb에 추가시키고, 리턴된다.

이것은 순열의 크기가 원하는 크기와 동일하게 되었다는 의미이다.

리턴되면, check [i]는 사용되지 않음으로 바뀌게 된다.

그전 트리로 돌아간다.

이를 반복한다. 

모든 과정이 끝났다면, sb에 추가된 배열의 순서를 출력한다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.