#1446 : 지름길

풀이방법

사용된 것:

정렬

다익스트라

 

2022.08.17

고속도로 위에서 0미터 지점부터 D미터 지점까지 1미터씩 전진하며,

현재 자신이 위치한 지점으로부터 시작하는 지름길이 있는지 확인하는 방법을 사용했다.

 

 

 

불필요한 연산을 줄이기 위해 다음과 같이 지름길 정보를 걸러서 저장했다.

주어진 지름길들 중

지름길의 도착지점이 고속도로의 끝지점을 초과하지 않고

이용했을 때 이득이 되는 것들만 List<지름길 클래스> list에 저장해둔다.

그리고

우리는 고속도로의 0미터 지점부터 차근차근 오름차순으로 진행해나갈 것이므로

지름길들을 시작지점을 기준으로 오름차순 정렬(시작지점이 같다면 끝지점을 기준으로 오름차순 정렬)한다.

 

 

 

다음으로는 다익스트라에 필요한 필드들을 준비한다.

 

1차원 정수 배열 dist를 선언한다. 이 배열은 각 지점들까지의 최단거리를 저장한다.

고속도로 위 P미터 지점까지의 최단거리는 dist[P] 에 저장되는 식이다.

선언하였으면 문제의 제한조건상 도출될 수 있는 상한 값인 10000을 모든 요소에 저장해둔다.

 

그리고 현재까지 반영이 완료된 지름길의 개수를 저장할 int형 변수 idx를 선언하고 0으로 초기화한다.

잘 정렬해둔 list의 가장 앞 순서인 지름길부터 하나씩 반영해나갈 것이다.

지름길 하나의 반영이 끝날 때마다 idx를 1씩 늘리는 방식이다.

 

 

 

이제 다익스트라를 시작한다.

 

아직 반영하지 않은 지름길이 남아있다면 list.get(idx)를 꺼내와 일단 손에 들고 있는다. 이 지름길 객체를 sc라 하겠다. sc는 우리가 진행해나가다 보면 가장 먼저 맞닥뜨릴 지름길의 정보를 가지고 있다.

 

이제 고속도로의 0미터 지점부터 1미터씩 나아가기 시작한다.

 

지름길 sc의 시작지점을 만나지 않는 동안에는 dist[지금 위치]를

Math.min((현재의 dist[지금 위치] 값), (dist[지금 위치 -1] +1))

으로 업데이트하고 넘어간다.

 

지름길 sc의 시작지점을 만났다면

dist[지름길 끝부분]의 값을

Math.min((현재의 dist[지름길 끝부분]의 값), (지름길을 사용했을 때 소요되는 거리))

로 업데이트한다.

 

시작지점 또는 도착지점이 서로 동일한 여러 개의 지름길이 존재할 수 있으므로, dist 값 업데이트 시에는 항상 Math.min을 사용해 최적의 값을 선택해야 한다.

 

코드

Java(2022.08.17)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//N과 D 읽어오기
		StringTokenizer st= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		
		//지름길 정보를 저장할 리스트
		List<Shortcut> list = new ArrayList<Shortcut>();
		
		//지름길 정보 읽어와 저장하기
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int len = Integer.parseInt(st.nextToken());
			
			//이용해봤자 이득이 없는 지름길은 저장하지 않음
			if(len >= e-s) continue;
			
			//역주행 불가이므로, 고속도로 끝지점보다 멀리 가는 지름길은 저장하지 않음
			if(e > d) continue;
			
			//나머지 경우에는 지름길 정보를 저장
			list.add(new Shortcut(s, e, len));
		}
		
		//지름길 정보를 시작지점이 이른 순으로,
		//시작지점이 같다면 끝지점이 이른 순으로 정렬
		Collections.sort(list, new Comparator<Shortcut>() {

			@Override
			public int compare(Shortcut o1, Shortcut o2) {
				// TODO Auto-generated method stub
				if(o1.getS() == o2.getS()) return o1.getE() - o2.getE();
				return o1.getS() - o2.getS();
			}
			
		});

		
		/**
		 * 여기부터 다익스트라 수행
		 */
		
		int idx = 0;	//현재까지 반영을 마친 지름길의 개수
		int[] dist = new int[10001]; 	//각 지점까지 최단거리
		Arrays.fill(dist, 10000);	//상한 값으로 채우기
		dist[0] = 0;	//출발지점의 값은 0
		
		//고속도로의 0미터 지점부터 d미터 지점까지 1미터씩 나아가며,
		//현재 지점에서 출발하는 지름길이 있을 경우 그것을 반영
		for(int moved = 0; moved<d+1; moved++) {
			
			//일단 1미터 이동
			if(moved != 0) dist[moved] = Math.min(dist[moved], dist[moved-1] +1);
			
			//이미 모든 지름길이 반영된 경우 그냥 넘어가기
			if(idx==list.size()) continue;
			
			
			//아직 반영하지 않은 지름길이 남은 경우 아래와 같이 수행
			
			Shortcut sc = list.get(idx);	//반영할 지름길
			//반영할 지름길의 시작지점이 현재 지점과 일치할 경우
			if(sc.getS() == moved) {
				//도착지점의 dist 업데이트
				dist[sc.getE()] = Math.min(dist[sc.getE()], dist[moved] + sc.getLen());
				
				idx++;
				moved--;	//이번 지점에서 출발하는 지름길이 또 있을지 모르므로 moved를 1 감소
			}
		}
		
		//정답 출력
		System.out.print(dist[d]);
		
	}

}


//지름길 정보를 저장하는 클래스
class Shortcut{
	private int s;	//시작지점
	private int e;	//끝지점
	private int len;	//길이
	
	public Shortcut (int s, int e, int len) {
		this.s = s;
		this.e = e;
		this.len = len;
	}
	
	public int getS() { return s; }
	public int getE() { return e; }
	public int getLen() { return len; }
}