백준 15649번
https://www.acmicpc.net/problem/15649

---

문제

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

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

---

입력

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

---

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

생각하기

프로그래머스의 단어변환 문제를 풀다가 여기로 왔다.
이유는 단어변환 문제 자체가 DFS/BFS 문제이긴 한데 백트래킹을 할 줄 알아야 풀 수 있는 문제였다.

그래서 백트래킹 개념을 공부하기위해서 N과M(1) 문제를 먼저 풀어보게 되었다.

솔직히 처음에 문제 내용보고 진짜 쉬울거라고 생각했는데
진짜 엄청 까다로운 문제였다.

그래서 다른 분들의 코드와 개념 정리한 글을 보고 공부한 후에 문제를 풀었다..

동작

동작은 재귀함수와 DFS()를 생각하면 그다지 어렵지 않지만
DFS() 함수에서 visit[i] = false 부분이 좀 많이 낯설게 느껴지고 복잡하게 만드는 주범이었던 것 같다.

visit과 arr이 변경되지만
arr[0]의 자리가 유지되면서 뒤의 내용이 계속 변경되는 것만 감을 잡으면 괜찮을 것 같다

재귀는 내가 설명하는 것보다 손으로 직접쏘보는 방식이 내가 설명하는 것보다 이해하기 더 좋은 방법이라고 생각한다.

이 문제풀면서 처음 알게된 점이 있었는데,
depth ++ 과 depth + 1 이 다르다는 점이다.

이문제를 풀 때 DFS(depth++)를 하면 틀린 값이 나오게된다.
이유를 얘기하자면

만약 depth = 4 라고 했을 때,
DFS(depth + 1) 로 실행하면 DFS(5)로 계산해서 depth의 4값은 변하지않고 5라는 값을 따로 실행하는 것이다.

하지만 DFS(depth++) 의 경우 depth의 값 자체가 5가 되었기 때문에 재귀가 끝나서 return 되어도 여전히 depth 는 5라는 값이 유지된다.

그래서 이 재귀함수에서는 ++와 + 1의 차이를 유의할 필요가 있다고 한다.

TMI

이게 겨우 실버? 말도 안돼..

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;

	static boolean visit[];
	static int arr[];

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new int[M];
		visit = new boolean[N];

		DFS(0);

		System.out.println(sb);
	} // End of main

	static void DFS(int depth) {

		if(depth == M) {
			for(int num : arr) {
				sb.append(num).append(' ');
			}
			sb.append('\n');
            return;
		}

		for(int i=0; i<N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = i + 1;
				DFS(depth + 1);
				visit[i] = false;
			}

		}

	} // End of DFS

} // End of class