[백준] 1446 지름길 - 동적계획법(DP, Dynamic Programming) + DFS(깊이우선탐색) JAVA

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

코드설명

동적계획법(DP, Dynamic Programming) + DFS(깊이우선탐색)을 활용합니다.

 

먼저 문제를 마주하고서, DFS 혹은 BFS를 활용하여 코드 작성이 가능하다는 점은 알 수 있습니다. 

그리고 이때 DFS를 활용할경우 최적부분구조(Optimial Substructure)가 성립함 또한 직관적으로 알 수 있습니다.

그런데, 이때 가장 신경쓰였던점은 스택 호출 개수입니다. 

만약 시작점 0 ~ 끝점 10000 이고, 아무런 지름길도 없는 상황이라고 합시다.

그럴경우 오직 DFS(now + 1) 을 통해서만 이동하게 되는데 이때 재귀호출 스택은 10000번 쌓입니다. 해당 부분이 신경스여서 BFS로 해야하나? 했지만 1만번이라 괜찮을 것 같아 DFS로 구현했습니다.(저의 경우 만약 호출횟수가 1만번 이상이라면 항상 고민하는데, 이 문제의 경우 최적 부분구조가 반드시 성립하기에 그대로 구현했습니다. 물론 스택에 쌓이는 메모리마다 가능한 스택호출 개수가 달라지지만 해당 사항까지 계산하기에는 부담스럽습니다. )

 

시간복잡도를 계산해보겠습니다.

1. 먼저 그래프 초기화입니다. 그래프 초기화는 O(10001) 입니다. O(D)이겠지요.

 

2. 간선 정보 입력입니다. 각 간선의 개수는 최대 12개입니다. O(N)입니다.

 

3. DFS 함수 입니다. DFS의 연산안에는 Graph[now]와 연결된 노드들의 개수는 최대 12개입니다. 그래서 O(N) 의 로직이 안에 존재하고, DFS 에서 매번 now + 1 연산이 실행되기에 이는 O(D) 입니다.

시간복잡도는 O(ND)입니다. 이떄 N은 12로 고정되어 있어 사실상 O(12 D) 입니다. 

사실 N은 12로 고정되어있어 더 줄어들지만 계산하기 애매하여 O(N D) 라고 합시다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static ArrayList<int[]>[] graph = new ArrayList[10001];
	static int[] cache = new int[10001];
	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());
		D = Integer.parseInt(st.nextToken());
		
		Arrays.fill(cache, -1);
		for(int i=0;i<10001; i++) {
			graph[i] = new ArrayList<int[]>();
		}
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			graph[A].add(new int[] {B, C});
		}
		
		
		System.out.println(DFS(0));
	}
	static int DFS(int now) {
		if(D<now) return 10001;
		if(D==now) return 0;
		if(cache[now] != -1) return cache[now];
		
		int ret = 10001;
		for(int connected = 0; connected < graph[now].size(); connected++) {
			int[] temp = graph[now].get(connected);
			int dest = temp[0];
			int dist = temp[1];
			ret = Math.min(ret, DFS(dest) + dist);
		}
		ret = Math.min(ret,  DFS(now + 1) + 1);
		
		return cache[now] = ret;
	}
	
}