[백준] 15649 N과 M(1)

Backtracking 문제는

 

설계

1. 문제를 어떻게 State Space Tree로 나타낼 것인가?

2. Promising Function은 어떻게 설정할 것인가?

 

구현

1. 재귀함수로 재귀적으로 트리를 탐색할 때 파라미터로 갱신해야하는 값은 있는가?

2. SST의 노드들의 방문과 되추적을 어떻게 코드로 나타낼 것인가?

3. 재귀함수의 basecase는 어떻게 설정해야 하는가?

 

설계상의 문제와 구현상의 문제를 모두 고려해야 한다.

 

 

설계 시도1 (실패)

 

설계 시도2 (성공)

 

설계1과 설계2의 차이는 "자식의 방문여부 기록"이다.

 

N=3 M=3 이면 1~3까지의 숫자를 중복없이 M개를 고른 수열이므로

answer = 123, 132, 213, 231, 312, 321이 될 것이다.

 

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

 

depth에 해당하는 자식 i(1 ~ 3)에 대해 방문할 때 (answer[depth] = i)

방문하기 전 해당 자식 i(1 ~ 3)을 이미 방문했는지 검사하고 (visit[i] == false)

방문을 안했을 경우에만 방문한다. 즉, visit[i] == false 자체가 promising function이 되는 것이다.

 

자식에 대해 방문했으니, 그 자식의 자식들에 대해 방문 즉, (depth + 1)에 대한 재귀호출이 일어나야 할 것이다.

 

해당 재귀호출이 basecase에 의해 추후 종료되면 그 재귀함수를 호출한 호출자로 거슬러올라가니 방문을 안한상태가 될 것이고(SST를 확인하자) 따라서 visit[i] = false로 방문안했음을 다시 표시해줘야 한다.

 

 

 

 

코드

package 백트래킹;

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

public class Pr15649 {
	static int N;
	static int M;
	static int[] answer;
	static boolean[] visit;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		visit = new boolean[N+1];
		answer = new int[M];
		
		dfs(0, answer);
		System.out.println(sb);
	}

	private static void dfs(int depth, int[] answer) {

		// base case
		if (depth == M) {
			for (int i=0; i<M; i++) {
				sb.append(answer[i]).append(' ');
			}
			sb.append('\n');
			return;
		}
		
		for (int i=1; i<=N; i++) {
			if (visit[i] == false) {
				answer[depth] = i;
				visit[i] = true;
				dfs(depth+1, answer);
				visit[i] = false;
			}
		}
	}
	
}

변수설명 (알고리즘 진행시 변수가 무엇을 의미하는지 스스로 정확히 파악해야한다.)

N: 고를 수 있는 숫자 1 ~ N

M: 수열의 수

boolean[ N+1 ] visit :  index에 해당하는 숫자1~N을 방문했는지 표시하기 위함

answer: 트리를 탐색하며 고른 수열 (depth == M 일때, 최종 수열)