[1446 지름길]

• 문제 - www.acmicpc.net/problem/1446

1446번: 지름길

 

• 분석 및 해결

단순한 bfs 문제였다. 지름길이 항상 |지름길 도착 위치 - 지름길 시작 위치| 보다 짧은 것은 아니라는 점을 주의해야 한다. 따라서, bfs를 통해 지름길을 이용하는 경우, 이용하지 않는 경우 모두에 대해서 탐색을 시도했다. 각 위치마다 모두 지름길을 가지고 있을 수도 있지만, 그렇지 않은 경우가 더 많을 거 같아 Map을 사용해서 graph를 구현했다.

 

• 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class BJ_1446 {

	private static int N, D;
	private static Map<Integer, List<int[]>> graph = new HashMap<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] param = br.readLine().split(" ");
		N = Integer.parseInt(param[0]);
		D = Integer.parseInt(param[1]);
		
		for(int iter = 0; iter < N; iter++) {
			param = br.readLine().split(" ");
			
			int src = Integer.parseInt(param[0]);
			int des = Integer.parseInt(param[1]);
			int dist = Integer.parseInt(param[2]);
			
			// src위치에 해당하는 지름길 정보가 없는 경우
			if(!graph.containsKey(src)) {
				graph.put(src, new ArrayList<>());
			}
			graph.get(src).add(new int[] {des, dist});
		}
		
		System.out.println(bfs());
	}

	private static int bfs() {
		int answer = 987654321;
		
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {0, 0});
		
		while(!q.isEmpty()) {
			int[] now = q.poll();
			
			// 목적지보다 위치가 먼 경우            
			if(now[0] > D) {
				continue;
			}
			
			if(now[0] == D) {
				answer = Math.min(answer, now[1]);
			}
			
			// 지름길을 이용하지 않고 다음 위치로 가는 경우            
			q.offer(new int[] {now[0] + 1, now[1] + 1});
			
			List<int[]> nextList = graph.get(now[0]);
			if(nextList != null) {
				for(int[] next: nextList) {
					q.offer(new int[] {next[0], now[1] + next[1]});
				}
			}
		}
		
		return answer;
	}
}