[백준 1446] 지름길 (Dijkstra, 다익스트라)

🧐 백준 1446. 지름길

문제

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

입력

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

예제

예제 입력	예제 출력
5 150 0 50 10 0 50 20 50 100 10 100 151 10 110 140 90	70
2 100 10 60 40 50 90 20	80
8 900 0 10 9 20 60 45 80 190 100 50 70 15 160 180 14 140 160 14 420 901 5 450 900 0	432

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

1446번: 지름길

 

💡 문제 풀이

다익스트라 유형의 문제이다. 오랜만에 접한 유형이어서 문제 풀이에 애를 좀 쓰긴 했지만, 풀다보니 익숙한 코드 구조를 볼 수 있었다.

 

우선 지름길을 저장하는 클래스를 정의해준다. 해당 클래스는 출발 지점(s), 도착 지점(e), 지름길의 길이(c)의 정보를 담고 있다.

도로를 역주행 할 수 없으므로, 출발 지점(출발 지점이 같다면 도착 지점)을 기준으로 오름차순 정렬하는 메소드를 오버라이딩 한다.

	static class Road implements Comparable<Road> {
		int s;
		int e;
		int c;

		Road(int s, int e, int c) {
			this.s = s;
			this.e = e;
			this.c = c;
		}

		@Override
		public int compareTo(Road o) {
			if (this.s == o.s) {
				return this.e - o.e;
			}
			return this.s - o.s;
		}
	}

 

도로 정보를 리스트 형식으로 저장한다.

여기서 "역주행 할 수 없다" 조건과 "지름길로 갔을 때의 길이가 일반 주행의 길이보다 클 수 없다" 조건을 필터링하여 저장해준다.

저장이 끝난 후에는 위에서 설정한 조건에 맞게 정렬해준다.

		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 c = Integer.parseInt(st.nextToken());
			if (s > e || (e - s) <= c) continue;
			al.add(new Road(s, e, c));
		}

		Collections.sort(al);

 

이제 다익스트라 알고리즘을 수행하면 된다.

거리 정보 배열(distance)을 정의한다. 세준이의 출발 지점은 0이므로 0에서 출발하는 기준으로 일차원 배열을 정의하고, 0번째 값을 0으로 초기화해준다. 반복문을 돌기 전에 지름길 리스트의 인덱스 값을 기억하는 값(idx)과 세준이의 실시간 이동 거리를 기억하는 값(move)을 초기화한다. 이후 세준이가 도착 지점(D)에 도달할 때까지 다익스트라 알고리즘을 수행한다.

		int[] distance = new int[10001];
		Arrays.fill(distance, 10001);
		distance[0] = 0;

		int idx = 0, move = 0;
		while (move < D) {
			if (idx < al.size()) {
				Road r = al.get(idx);
				if (move == r.s) {
					distance[r.e] = Math.min(distance[r.e], distance[move] + r.c);
					idx++;
					continue;
				}
			}
			distance[move + 1] = Math.min(distance[move + 1], distance[move] + 1);
			move++;
		}

지름길 리스트를 모두 방문할 때까지(idx < al.size()) 지름길을 사용하는 경우를 따진다.

만약 세준이가 현재 위치하는 지점(move)이 지름길의 시작 지점(r.s)과 같다면, 지름길을 이용했을 경우와 그렇지 않은 경우를 비교해서 거리 배열(distance[r.e])을 업데이트 시킨다. 지름길을 사용했으면 idx++하여 리스트의 위치 값도 업데이트 해주어야 한다.

지름길을 이용했다면 continue를 사용해서 다음 지점으로 넘어가고, 사용하지 않았다면 일반 도로를 사용한 경우를 따져야한다.

세준이가 도로의 1만큼 갔을 경우의 거리 위치 배열(distnace)을 비교해서 업데이트 해준다. 한 칸 갔으면 move++하여 세준이가 이동한 거리를 업데이트 시킨다.

 

다익스트라 알고리즘 수행 이후 세준이의 목표 지점의 최단 거리(distance[D])를 구할 수 있다.

위 풀이 방식을 전체 알고리즘으로 풀어내면 아래와 같다.

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

public class 지름길_1446 {

	static class Road implements Comparable<Road> {
		int s;
		int e;
		int c;

		Road(int s, int e, int c) {
			this.s = s;
			this.e = e;
			this.c = c;
		}

		@Override
		public int compareTo(Road o) {
			if (this.s == o.s) {
				return this.e - o.e;
			}
			return this.s - o.s;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());

		List<Road> al = new ArrayList<>();

		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 c = Integer.parseInt(st.nextToken());
			if (s > e || (e - s) <= c) continue;
			al.add(new Road(s, e, c));
		}

		Collections.sort(al);

		int[] distance = new int[10001];
		Arrays.fill(distance, 10001);
		distance[0] = 0;

		int idx = 0, move = 0;
		while (move < D) {
			if (idx < al.size()) {
				Road r = al.get(idx);
				if (move == r.s) {
					distance[r.e] = Math.min(distance[r.e], distance[move] + r.c);
					idx++;
					continue;
				}
			}
			distance[move + 1] = Math.min(distance[move + 1], distance[move] + 1);
			move++;
		}

		System.out.println(distance[D]);

	}
}

 

✨ 포스팅을 마치며

다익스트라 알고리즘은 어느정도 익숙해졌다고 생각했는데 막상 오랜만에 접하니까 문제에 적용시키는 것이 어렵게 느껴졌다. 다시 꾸준히 문제를 풀어야겠다. 이번 문제도 클래스를 사용하니까 가독성과 정렬 모두 단순화되어 좋았다.