[백준 #1446] 지름길 - JAVA(자바)

문제

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

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

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

해설

N의 최대 크기가 12이기 때문에 모든 경우를 고려해도 된다고 생각했다. 그래서 BFS를 이용해서 가능한 경로를 모두 비교했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        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<Path> list = 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 dist = Integer.parseInt(st.nextToken());
            if(e > d) continue; //  e > d 인 지름길은 필요없음.
            if(e - s < dist) continue; // 지름길이 더 멀 경우 필요없음.
            list.add(new Path(s, e, dist));
        }
        Collections.sort(list, (o1, o2) -> o1.s - o2.s); // 시작점을 기준으로 오름차순 정렬
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0));
        int answer = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            Node cur = q.poll();
            answer = Math.min(answer, cur.dist + d - cur.pos); // 현재까지 이동 거리 + 현재 위치에서 목표 지점까지 거리
            for (Path path : list) {
                if(path.s < cur.pos) continue; // 지름길이 현재 위치보다 뒤에 있는 경우
                int go = path.s - cur.pos; // 현재 위치에서 지름길까지 가는 거리
                int nextPos = path.e;
                int nextDist = cur.dist + go + path.dist; // 총 이동 거리
                q.add(new Node(nextPos, nextDist));
            }
        }
        System.out.println(answer);
    }
}

class Node{
    int pos; // 현재 위치
    int dist; // 거리 총합

    public Node(int pos, int dist) {
        this.pos = pos;
        this.dist = dist;
    }
}

class Path{
    int s;
    int e;
    int dist;

    public Path(int s, int e, int dist) {
        this.s = s;
        this.e = e;
        this.dist = dist;
    }
}