백준 15650, N과 M(2) - Backtracking

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

1. 아이디어

• for문에서 1 ~ n 까지 자연수 차례로 확인
• 백트래킹 재귀함수
  • 아직 방문(선택)하지 않았고, 이전에 선택한 수 보다 더 큰 수 선택
  • 종료 조건: 선택한 숫자 개수(재귀호출 트리 depth) == m
  • 재귀함수 호출 종료 후 복귀하여 방문 확인 배열 복구, 최근에 선택한 수 복구

2. 자료구조

• boolean[]: 1 ~ n 선택(방문) 확인
• 선택한 숫자들 저장
  방법 ① Stack<Integer>
  방법 ② int[]

3. 시간 복잡도

Backtracking의 시간 복잡도

1) 중복 있는 경우: O(n^n)

• n <= 8 까지 가능

2) 중복 없는 경우: O(n!)

• n <= 10 까지 가능
  => n 최대값 대입: 8! = 40,320 << 1억 (1초)

코드 ① - Stack에 선택한 숫자들 저장

import java.io.*;
import java.util.StringTokenizer;
import java.util.Stack;

public class Main_Stack {
	static int n, m;		// 1 ~ n 까지 자연수, 중복없이 m개 선택 (오름차순)
	static boolean[] check;		// 1 ~ n 까지 자연수 선택 여부
	static Stack<Integer> selectedNumbers = new Stack<>();		// 선택된 숫자들

	/* depth: 현재까지 선택한 숫자 개수, 백트래킹 재귀 호출(트리)에서의 깊이 */
	static void solution(int depth) {
		// 재귀함수 종료 조건
		if (depth == m) {
			for (int number : selectedNumbers)
				System.out.print(number + " ");
			System.out.println();
			return;
		}

		for (int i = 1; i <= n; i++) {
			// 아직 방문하지 않았고, 이전에 선택한 수 보다 더 큰 수 선택
			if (!check[i] &&
					(depth == 0 || i > selectedNumbers.peek())) {
				// depth == 0 대신 selectedNumbers.isEmpty() 가능
				check[i] = true;
				selectedNumbers.push(i);
				solution(depth + 1);

				// 재귀함수 호출 종료 후, 복귀 시점
				check[i] = false;
				selectedNumbers.pop();
			}
		}
	}

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		check = new boolean[n + 1];		// [1 ~ n] 사용

		solution(0);
	}
}

코드 ② - 배열 int[]에 선택한 숫자들 저장

import java.io.*;
import java.util.StringTokenizer;

public class Main_Arr {
	static int n, m;			// 1 ~ n 까지 자연수, 중복없이 m개 선택 (오름차순)
	static boolean[] check;			// 1 ~ n 까지 자연수 선택 여부
	static int[] selectedNumbers;		// 선택된 숫자들

	/* depth: 현재까지 선택한 숫자 개수, 백트래킹 재귀 호출(트리)에서의 깊이 */
	static void solution(int depth) {
		// 재귀함수 종료 조건
		if (depth == m) {
			for (int num : selectedNumbers)
				System.out.print(num + " ");
			System.out.println();
			return;
		}

		for (int i = 1; i <= n; i++) {
			// 아직 방문하지 않았고, 이전에 선택한 수 보다 더 큰 수 선택
			if (!check[i] &&
					(depth == 0 || i > selectedNumbers[depth - 1])) {
				check[i] = true;
				selectedNumbers[depth] = i;
				solution(depth + 1);

				// 재귀함수 호출 종료 후, 복귀 시점
				check[i] = false;
			}
		}
	}

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		check = new boolean[n + 1];		// [1 ~ n] 사용
		selectedNumbers = new int[m];

		solution(0);
	}
}

Backtracking 으로 선택한 item들을 Stack에 저장하는 방법과 배열 int[]에 저장하는 방법의 차이점

1. Stack에 저장

• 재귀 호출 종료 후 복귀하여, 가장 최근에 선택한 item을 Stack에서 pop 명시 해주어야 함

2. 배열 int[]에 저장

• 재귀 호출 종료 후 복귀하여, 가장 최근에 선택한 item을 int[]에서 직접 제거 명시하지 않아도 됨
• 재귀 호출의 depth를 배열 index로 사용하여, arr[depth]에 자연스럽게 다른 item으로 채워짐