Calm Dawn Studio

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

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

public class Main {

	static BufferedReader br;
	static BufferedWriter bw;
	static int N, M;
	static int[] answer;
	
	public static void main(String[] args) throws IOException {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 1 ~ N 자연수 중
		M = Integer.parseInt(st.nextToken()); // 중복없이 M개 고르기
		answer = new int[M];					//정답을 담아둘 배열
		
		boolean[] isUsed = new boolean[N + 1]; // 해당 숫자가 사용되었는지 확인하기 위한 배열
												// 숫자가 사용된 경우 true, 미사용된 경우 false
		int depth = 0; // 수열의 길이
		
		solution(isUsed, depth);
		
		bw.flush();
		bw.close();

	}

	private static void solution(boolean[] isUsed, int depth) throws IOException {
		if (depth == M) { // 수열의 길이가 M과 같다면 출력함
			for(int i=0; i<answer.length; i++) {
				bw.write(answer[i]+ " ");
			}
			bw.newLine();
			return;
		}

		for (int i = 1; i <= N; i++) {
			if (isUsed[i] == false) {
				isUsed[i] = true;
				answer[depth] = i;
				solution(isUsed, depth + 1);
				isUsed[i] = false;
			}
		}

	}
}

가장 처음 접하는 백트래킹 문제로 답을 이해하는 과정까지 정말 어려웠다. (이 문제가 정답율 60%라니!! )

처음 문제에 접근한 방식

1. 어떻게 구현해야할지 감도 잡지못해서 단순 배열에 값을 저장함

2. 구하고자 하는 수의 개수만큼, 모든 수를 반복문으로 확인하다보니 시간초과 발생

정답을 맞춘 풀이방법

1. M개를 고르니 정답을 담아 출력할 배열 선언

2. 숫자가 사용되었는지 확인할 boolean형 배열 선언,  각 숫자가 사용될때마다 배열의 깊이(길이) 값을 +1하여 넘김

3. 숫자가 사용시 true 이후 false를 해주지 않으면 true인 모든 값이 호출됨

4. 배열의 깊이 = 구하고자하는 M의 개수라면 정답을 출력함

사용된 수의 자리수를 구분하기 위해 정답을 담을 별도의 배열 선언