15649. N과 M (1) (자바, Java)

 백트래킹 알고리즘 첫걸음.

나중에 알았는데, 3대 뉴비절단기로 재귀, 백트래킹, 동적계획법이 있다고 한다.

나도 알고리즘 공부 첫 위기가 재귀 (별찍기+하노이의탑)에서 왔고, 거기를 극복하고 백트래킹에서 한차례 위기가 와서 잠깐 다른 문제 풀다 다시 도전했다.

 

 백트래킹은 모든 경우의 수를 탐색하나, brute-force와는 달리, 뻔히 가망없어보이는 경우는 탐색을 생략하고 다음 단계의 탐색을 진행한다.

 

 나의 경우, 설명을 듣고 끄덕끄덕하긴 했으나, 정작 문제를 보고 아무생각이 안나서 멘탈이 터졌던 기억이 있다. 첫 문제는 그냥 클론코딩으로 해결했고, 이후 n과m 시리즈를 해결하면서 깨달음을 얻은 케이스다. 혹여라도 나처럼 어려움을 겪은 분들이 있다면, 같은 방법을 추천드린다.

또한, 코드만으로는 그림이 잘 안 그려지기 때문에, 필기를 이용해 어느정도 스케치하고 설계해보는걸 추천한다.

 

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

public class Main {

	static int n, m;
	static int[] arr;
	static StringBuilder sb = new StringBuilder();
	static int depth;
	static boolean[] visit;
	
	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());
		visit = new boolean[n];
		arr = new int[m];
		
		dfs(0);
		System.out.println(sb);		
	}
	
	static void dfs(int depth) {		
			if (depth==m) {
				for (int j : arr) {
					sb.append(j + " ");					
				}
				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;
				}
			}
	}
}