[백준_1446번] 지름길

[문제]

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

 

[입력 조건]

• 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

 

[코드]

import java.util.*;

class Node_20922 {
	int start,end,cost;
	
	public Node_20922(int start, int end, int cost) {
		this.start=start;
		this.end=end;
		this.cost=cost;
	}
}

public class BaekJoon_20922 {
	static ArrayList<Node_20922> info=new ArrayList<>();
	static int[] distance=new int[10001]; // 각 노드까지의 최단거리 저장 배열
	static int n,d;
 	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		d=sc.nextInt();
		
		while(n-->0) {
			int s=sc.nextInt();
			int e=sc.nextInt();
			int c=sc.nextInt();
			
			if(e-s<=c)// 지름길이 아닌 경우
				continue;
			
			info.add(new Node_20922(s,e,c));
		}
		
		Collections.sort(info, new Comparator<Node_20922>() {

			@Override
			public int compare(Node_20922 o1, Node_20922 o2) {
				// 시작점이 빠른 순서대로 정렬 -> 시작점이 같은 경우 도착지점이 빠른 순서
				if(o1.start==o2.start)
					return  o1.end-o2.end;
				
				return o1.start-o2.start;
			}
			
		});
		
		Arrays.fill(distance,Integer.MAX_VALUE); // 초기화
		distance[0]=0; // 시작지점
		
		// info 리스트의 인덱스, 현재 도달한 위치
		int index=0,now=0;
		while(now<d) { 
			if(index<info.size()) { // 지름길 탐색
				Node_20922 road=info.get(index);
				if(now==road.start) { // 현재 위치한 곳이 지름길이 있는 경우라면
					// 지름길을 통하여 이동하는 경우 or 지름길을 이용하지 않는 경우 중 이동거리가 더 적은 경우 선택
					distance[road.end]=Math.min(distance[now]+road.cost,distance[road.end]);
					index++;
				}
				else { // 지름길이 없는 경우
					// 다음칸으로 이동하는 최단거리 구하기
					distance[now+1]=Math.min(distance[now+1],distance[now]+1);	
					now++;
				}
					
			}
			else { // 더 이상 탐색할 지름길이 없는 경우
				distance[now+1]=Math.min(distance[now+1],distance[now]+1);	
				now++;
			}
		}
		System.out.println(distance[d]);
	}

}

 

[고찰]

 정말 오랜만에 다익스트라 문제를 접해봐서인지 개념조차 잘 떠오르지 않아 다익스트라 관련 개념과 코드를 먼저 공부한 후에 문제를 풀어보았다. 그래도 코드 오류가 떠서 다른 사람의 코드를 참고하며 해결하였다. 

 각 노드에 도달하기까지의 최단거리를 저장한 distance 배열을 최댓값으로 초기화 한 후 모든 지점에서 지름길이 있나 확인하고, 만약 지름길이 있다면 지름길을 이용하는 경우와 아닌 경우를 비교해가며 distance 배열을 갱신하는 방식으로 해결해야 했다. 

 기본 알고리즘 개념을 까먹지 않도록 관련 문제들을 자주 풀어봐야겠다는 생각이 들었다..