[백준] 14496 그대, 그머가 되어 - DFS(깊이우선탐색) + BFS(너비우선탐색) JAVA

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

코드설명

DFS(깊이우선탐색) + BFS(너비우선탐색) 을 활용합니다.

 

처음에 문제를 보고, DFS로 최대한 빠르게 a가 b로 가는 지점을 찾는 것 아니야? 라는 생각으로 바로 DFS로 구현했습니다.

하지만, 이 과정에서 DFS로 다른 방향에서 b로 먼저 가는경우 visited[next] = false로 다시 원상복구 해야만 올바르게 탐색합니다. 

또 다시, 이렇게 visited[next] = false를 통해 모든 구간을 다 확인하면 2^1000 의 시간복잡도가 됩니다. 문제의 구조를 보면 최적 부분 구조(Optimal Substructure)라는 것을 직관적으로 알 수 있습니다. 이를 메모이제이션 cache 배열을 활용하여 시간초과를 벗어납니다.

 

위와 같이 하는 것보다는 사실 BFS로 각 탐색 Size를 Control 하여 가장 빨리 BFS로 한단계씩 찾아나가도록 구현하는 것이 더 간단한 방식입니다.

 

또, 문제에서는 양방향 간선이라는 조건이 없는데, 양방향 간선으로 해야합니다.

코드

DFS로 푼 코드입니다. (BFS로 푼다면 더 간단히 풀 수 있습니다.)

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, B, a, b;
	static int answer = 0;
	static int[][] matrix;
	static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		a = Integer.parseInt(st.nextToken()) - 1;
		b = Integer.parseInt(st.nextToken()) - 1;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		matrix = new int[N][N];
		cache = new int[N];
		Arrays.fill(cache, -1);
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken()) - 1; 
			int v2 = Integer.parseInt(st.nextToken()) - 1;
			
			matrix[v1][v2] = 1;
			matrix[v2][v1] = 1;
		}
		boolean[] visited = new boolean[N];
		visited[a] = true;
		answer = dfs(0, a, b, visited);
		System.out.println(answer > 1000 ? -1 : answer);
		
	}
	static int dfs(int depth, int now, int target, boolean[] visited) {
//		System.out.println("now:"+now+"target:"+target);
		if(now == target) {
			return 0;
		}
		
		if(cache[now] != -1) return cache[now];
		int ret = 1001;
		for(int next=0;next<N;next++) {
			if(matrix[now][next] == 1 && visited[next] == false) {
				visited[next] = true;
				ret = Math.min(ret, dfs(depth + 1, next, target, visited) + 1);
				visited[next] = false;
			}
		}
		return cache[now] = ret;
	}
	
	
}