[BOJ 백준] 지름길 (자바 풀이, 그리디, 다익스트라)

📌 문제

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

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

⚔ 제한 사항

입력

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

출력

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

예시

👀 문제 해석

고속도로의 길이 D ㎞가 주어진다. 매 1 ㎞마다 좌표 0 ~ D 까지 번호를 매겨 한 줄로 늘어놓고, 몇몇 구간에는 일방통행 지름길이 놓여 있다. 지름길은 시작 좌표 → 끝 좌표 (길이 ℓ) 로 표현되는데, ℓ이 원래 거리(끝−시작)보다 짧을 때에만 “지름”이라는 이름값을 한다. 우리는 0에서 출발해 역주행 없이 D까지 달린다. 매번 1 ㎞ 직선으로 가거나, 지금 서 있는 좌표에서 시작하는 지름길을 탈 수 있다. 목적지까지 총 주행 거리를 최소화하는 것이 목표다.

이 구조를 뜯어 보면 본질은 가중치가 있는 단방향 그래프의 최단 경로 문제다. 모든 좌표를 정점으로, 직선 1 ㎞ 이동과 지름길을 간선으로 놓으면 그래프가 완성된다. 정점 수가 최대 10001(0~D)이고 지름길도 많아야 12개라서, 최단 경로 알고리즘 중에서도 다익스트라가 가장 자연스럽다. 좌표가 연속적·선형적이라는 점에 착안하면 1차원 DP(dp[i] = 0→i 최단 거리)로도 풀 수 있고, 두 방법 모두 시간 복잡도는 여유롭다.

🔎 접근

“혹시 눈앞 지름길만 타면 되지 않을까?”

처음에는 지름길만 보아도 문제를 풀 수 있을 것 같아서, 눈앞에 보이는 지름길을 우선적으로 선택하는 그리디 방식이 가능한지 살펴보았다.

예를 들어 다음과 같은 방식이다.

지금 좌표에서 시작하는 지름길이 있으면 그중 가장 멀리 보내 주는(=끝 좌표가 큰) 놈을 고른다.

없다면 얌전히 1 ㎞ 직진.

D에 도착할 때까지 반복.

예를 들어, 문제의 첫 번째 예시의 경우 다음과 같은 그리디 접근으로 정답 70을 정확히 도출해낸다.

<svg width="720" height="180" viewBox="-20 -20 520 140"
     xmlns="http://www.w3.org/2000/svg"
     font-family="sans-serif" font-size="12">
  <!-- 고속도로 -->
  <line x1="0" y1="60" x2="450" y2="60" stroke="black" stroke-width="2"/>
  <!-- 눈금과 좌표 -->
  <g stroke="black">
    <line x1="0"   y1="50" x2="0"   y2="70"/>
    <text x="-5"  y="90">0</text>
    <line x1="150" y1="50" x2="150" y2="70"/>
    <text x="145" y="90">50</text>
    <line x1="300" y1="50" x2="300" y2="70"/>
    <text x="295" y="90">100</text>
    <line x1="450" y1="50" x2="450" y2="70"/>
    <text x="445" y="90">150</text>
  </g>

  <!-- 지름길: 0→50 (10㎞)  ─ 선택 -->
  <path d="M0,60 Q75,0 150,60" fill="none" stroke="crimson"
        stroke-width="3" marker-end="url(#arrow)"/>
  <text x="60" y="10" fill="crimson">10㎞</text>

  <!-- 지름길: 0→50 (20㎞) ─ 무시 -->
  <path d="M0,60 Q75,20 150,60" fill="none" stroke="lightgray"
        stroke-dasharray="4 4"/>
  <text x="60" y="30" fill="gray">20㎞</text>

  <!-- 지름길: 50→100 (10㎞) ─ 선택 -->
  <path d="M150,60 Q225,10 300,60" fill="none" stroke="crimson"
        stroke-width="3" marker-end="url(#arrow)"/>
  <text x="210" y="10" fill="crimson">10㎞</text>

  <!-- 지름길: 110→140 (90㎞) ─ 무시 -->
  <path d="M330,60 Q375,20 420,60" fill="none" stroke="lightgray"
        stroke-dasharray="4 4"/>
  <text x="360" y="30" fill="gray">90㎞</text>

  <!-- 화살표 정의 -->
  <defs>
    <marker id="arrow" viewBox="0 0 10 10" refX="10" refY="5"
            markerWidth="6" markerHeight="6" orient="auto-start-reverse">
      <path d="M0,0 L10,5 L0,10 Z" fill="crimson"/>
    </marker>
  </defs>

  <!-- 범례 -->
  <rect x="0" y="110" width="16" height="6" fill="crimson"/>
  <text x="22" y="116">지름길(그리디가 선택)</text>
  <rect x="200" y="110" width="16" height="6" fill="lightgray"/>
  <text x="218" y="116">지름길(무시됨)</text>
</svg>

그런데 항상 그럴까? 즉, "매번 지름길이 등장하면 무조건 선택해서 가는 게 전체 거리도 최소가 될까?" 예컨대 아래처럼 짧은 길이 있다고 상상해보자.

고속도로 길이: 10
지름길①: 0 → 5 (길이 3)
지름길②: 3 → 10 (길이 4)

이 상황에서 그리디로 접근하면 어떻게 될까? 처음 출발지점인 0에서 봤을 때, 지름길①은 매우 매력적이다. 무려 원래 거리 5를 3으로 단축시켜준다. 그리디 방법은 자연스럽게 이 지름길을 선택한다. 이렇게 되면 0→5까지 3㎞, 이후 목적지 10까지 직선으로 5㎞를 달려 총 8㎞가 된다.

그런데 이 선택이 과연 최적일까? 다시 따져보자. 만약, 지름길①을 타지 않고 조금 더 직진해 3까지 간 후 지름길②를 탔다면 어떻게 되었을까? 직선으로 0→3까지 3㎞, 그리고 지름길②로 3→10까지 4㎞를 더하면 총 거리가 7㎞가 된다.

<svg width="600" height="200" xmlns="http://www.w3.org/2000/svg">

  <!-- 도로 기본선 -->
  <line x1="50" y1="100" x2="550" y2="100" stroke="#ccc" stroke-width="4"/>

  <!-- 좌표 표시 -->
  <circle cx="50" cy="100" r="5" fill="#444"/>
  <text x="45" y="120" font-size="12">0</text>

  <circle cx="200" cy="100" r="5" fill="#444"/>
  <text x="195" y="120" font-size="12">3</text>

  <circle cx="300" cy="100" r="5" fill="#444"/>
  <text x="295" y="120" font-size="12">5</text>

  <circle cx="550" cy="100" r="5" fill="#444"/>
  <text x="545" y="120" font-size="12">10</text>

  <!-- 지름길① (0→5) -->
  <path d="M 50,95 Q 175,10 300,95" stroke="#FF6B6B" fill="none" stroke-width="3" marker-end="url(#arrow)"/>
  <text x="160" y="40" font-size="12" fill="#FF6B6B">지름길①(길이3)</text>

  <!-- 지름길② (3→10) -->
  <path d="M 200,95 Q 375,10 550,95" stroke="#4D96FF" fill="none" stroke-width="3" marker-end="url(#arrow)"/>
  <text x="330" y="40" font-size="12" fill="#4D96FF">지름길②(길이4)</text>

  <!-- 마커 정의 -->
  <defs>
    <marker id="arrow" markerWidth="10" markerHeight="10" refX="6" refY="3" orient="auto" markerUnits="strokeWidth">
      <path d="M0,0 L0,6 L9,3 z" fill="#888" />
    </marker>
  </defs>

  <!-- 설명 글씨 -->
  <text x="50" y="150" font-size="12">그리디 선택: 0→5 (지름길①) + 5→10 직진 = 총 8㎞</text>
  <text x="50" y="170" font-size="12">최적 선택: 0→3 직진 + 3→10 (지름길②) = 총 7㎞</text>

</svg>

즉, "눈앞에 있는 가장 좋은 지름길을 무조건 타는 것이 전체 최단거리를 보장하지 않는다"는 사실을 명확히 알 수 있다. 다음과 같은 두 가지 사실이 도출된다.

(1) 현위치에서 가장 좋아 보이는 선택이 전역 최적을 보장하지 않는다.

(2) 결국 ‘전체 지도를 한꺼번에’ 바라보는 알고리즘이 필요하다.

대안은 무엇일까?

그래프 관점에서 다시 바라보는 것이 필요했다. 직선도로의 특성상, 도로 위의 각 좌표들을 일종의 그래프의 노드로 생각할 수 있다. 각 지점에서 다음 지점으로 넘어가는 움직임은 간선으로, 지름길 역시 특정한 좌표를 연결하는 가중치가 있는 간선으로 생각하면, 이 문제는 명확한 ‘단방향 가중치 그래프의 최단 경로 문제’가 된다.

그렇다면 이제 생각은 자연스럽게 다익스트라 알고리즘으로 흐른다. 그리고 다음과 같은 알고리즘을 생각해볼 수 있다.

dist[0] = 0 으로 시작해 우선순위 큐에 (pos=0, cost=0) 삽입.
큐에서 가장 싼 노드를 꺼낸다.
① 1㎞ 직진 간선: pos+1 로 가는 비용 +1 을 계산해 dist 를 갱신.
② 지름길 간선: 현 위치에서 출발 가능한 지름길들을 순회하며 동일하게 갱신.
큐가 빌 때까지 2~4 반복.

한가지 짚고갈 부분은 "정점이 많고 간선의 수가 많아질 수도 있는데, 다익스트라를 돌리는 게 괜찮을까?" 라는 점이다. 문제의 조건을 살펴보면 최대 좌표 수는 10,000개 정도이고 지름길이 최대 12개밖에 안된다. 즉, 실제 고려해야 할 간선은 생각보다 많지 않고, 다익스트라 알고리즘으로 충분히 빠르게 처리할 수 있음을 확인할 수 있다.

“다익스트라 대신 DP는 어떨까?”

이 문제는 1차원 선이기 때문에, dp[i] = 0에서 i까지의 최단 거리라는 식으로도 해결이 가능하다. i가 0에서부터 커질 때마다 dp[i+1] = min(dp[i+1], dp[i]+1)와 같이 1㎞ 직선 이동을 고려하고, 모든 지름길에 대해서도 dp[end] = min(dp[end], dp[start] + ℓ)로 갱신하면 될 것이다.

다만 DP나 다익스트라 모두 구현 난이도와 시간복잡도 면에서 큰 차이는 없을 것으로 보고, 다익스트라 방식을 택해도 무방하다고 생각했다. 직관적으로 그래프라는 개념을 가져오는 것이 편해서 다익스트라를 구현했다.

💡 풀이 코드

1️⃣ 데이터 입력과 전처리

우선 입력 데이터를 받아서, 사용할 지름길만 유효성 검증을 거쳐 저장한다. 지름길은 실제 도로의 원래 길이보다 짧고, 도착 지점이 목적지 D 이내인 경우만 유효하다.

다음과 같은 예제 입력에 대해서, 맨 첫 번째만 살펴보면

n	5	지름길 다섯 개
D	150	좌표 0 ~ 150

이후 while (n-- > 0) 루프에서 “진짜 지름길” 만 list 에 모은다.

c < b-a	원래 거리보다 짧을 때만 지름길
b <= D	종착지를 넘겨 버리는 길은 의미 없음

유효 지름길만 필터링되어 다음과 같이 저장된다.

(0 → 50, 10㎞), (0 → 50, 20㎞), (50 → 100, 10㎞), (110 → 140, 90㎞)
(100 → 151)은 목적지(150)를 초과하므로 제외됨

2️⃣ 그래프 구성

각 지름길은 출발점을 기준으로 한 그래프로 변환하여 표현한다.

// 2) 그래프 생성: 0부터 D까지 각 위치를 노드처럼 간주
List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i <= D; i++) {
    graph.add(new ArrayList<>());
}

// 2-1) 지름길 정보를 그래프에 반영
for (Node node : list) {
    int start = node.start;  // 지름길 시작
    int end = node.end;      // 지름길 끝
    int d = node.cost;       // 지름길 길이

    // start 에서 end 로 가는 간선을 등록
    // => graph.get(start) 에 Node(start, end, d) 추가
    graph.get(start).add(new Node(start, end, d));
}

graph[i] ⇒ 좌표 i 에서 출발하는 지름길 목록
직선 1 ㎞ 간선은 넣지 않는다 → 루프 내부에서 즉석으로 처리할 예정

graph[0] → [(0, 50, 10), (0, 50, 20)]
graph[50] → [(50, 100, 10)]
graph[110] → [(110, 140, 90)]

각 인덱스(0~D)는 좌표를 나타내고, 그 좌표에서 시작하는 지름길들이 리스트로 묶인다.

3️⃣ 거리 배열과 PQ 초기화

출발점인 0에서 각 지점까지의 최소 거리를 저장할 배열을 무한대로 초기화하고 출발점만 0으로 설정한다.

int[] dist = new int[D + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;  // 출발지점(0)까지의 최단거리는 0

PriorityQueue<State> pq = new PriorityQueue<>();
pq.offer(new State(0, 0));  // 위치=0, 비용=0 을 큐에 삽입

그리고 우선순위 큐에 출발 상태 (좌표 0, 거리 0)을 넣는다.

여기서 State는 현재 위치와 출발점으로부터 누적된 거리를 저장하는 객체다. 다익스트라 알고리즘에서 우선순위 큐는 항상 가장 거리가 짧은 상태를 우선 탐색하기 위해 사용되므로, State는 다음과 같이 설계했다.

static class State implements Comparable<State> {
    int x;      // 현 위치 (0 ~ D)
    int cost;   // 출발점(0) → x 까지 누적 이동 거리

    State(int x, int cost) {          // 생성자
        this.x    = x;
        this.cost = cost;
    }

    /*  우선순위 큐에서 '누적 비용이 작은 순' 으로 꺼내기 위해  */
    @Override
    public int compareTo(State o) {
        return Integer.compare(this.cost, o.cost);
    }
}

Comparable 인터페이스를 구현함으로써, 우선순위 큐가 자동으로 누적 비용이 적은 상태를 우선적으로 처리하도록 했다. 즉, 항상 가장 효율적인(거리가 짧은) 상태가 먼저 큐에서 추출된다.

각 필드의 의미는 다음과 같다.

x	정점 ID지금 서 있는 고속도로 좌표	다음 간선을 고르려면 “현재가 어디인지” 반드시 알아야 한다.
cost	거리 누계출발점에서 여기까지 최단 거리	다익스트라는 “가장 싸게 도달한 정점부터 확정” 하는 알고리즘이므로, 우선순위 큐의 키 로 쓰인다.

배열 int[2] 를 써도 되지만
이름 없는 [x, cost] 보다 state.x, state.cost 처럼 의미가 드러나 코드를 읽기 쉽다.
compareTo 로 “cost 오름차순” 정렬 규칙을 한번만 써두면,
우선순위 큐 생성 때 Comparator 를 따로 넘길 필요도 없다.

이제 초기 상태는 다음과 같다.

초기 상태: pq = [(0, 0)], dist[0] = 0, 나머지 dist[]는 무한대

4️⃣ 다익스트라 알고리즘의 핵심 반복

이제 본격적으로 다익스트라 탐색을 시작해보자.

우선순위 큐가 빌 때까지 가장 싼 상태를 추출하고 다음 두 가지 상황을 고려해 거리를 갱신한다.

(1) 1㎞ 직진 이동

// 1km씩 직진으로 이동 가능한 경우
if (도착지점까지도달하지못했고(currentX, D) && 더짧은거리인가(currentCost + 1, dist[currentX + 1])) {
    dist[currentX + 1] = currentCost + 1;
    pq.offer(new State(currentX + 1, dist[currentX + 1]));
}

예를 들어, 현재 좌표가 0이고 누적거리가 0이라면, 직선 이동 시 좌표 1까지 거리는 1로 업데이트되고 상태 (1, 1)이 큐에 추가된다.

(2) 지름길 사용

// 현 위치에서 출발 가능한 모든 지름길 탐색
for (Node 지름길 : graph.get(currentX)) {
    if (더짧은거리인가(currentCost + 지름길.cost, dist[지름길.end])) {
        dist[지름길.end] = currentCost + 지름길.cost;
        pq.offer(new State(지름길.end, dist[지름길.end]));
    }
}

예시 입력 1의 경우,

0 좌표에서 지름길 (0→50, 비용=10)과 (0→50, 비용=20)이 있다.
이 중 가장 짧은 (0→50, 비용=10)이 적용되어 dist[50]이 10으로 갱신된다. 상태 (50, 10)이 큐에 추가된다.

상태가 갱신되는 상황을 시각화화면 다음과 같다.

<!-- 다익스트라 첫 3-스텝: PQ·dist 변화 과정 -->
<svg width="640" height="240" xmlns="http://www.w3.org/2000/svg" font-family="sans-serif">

  <!-- 단계 타이틀 -->
  <text x="70"  y="24" font-size="14" font-weight="bold">① 초기</text>
  <text x="245" y="24" font-size="14" font-weight="bold">② 좌표 0 탐색 후</text>
  <text x="450" y="24" font-size="14" font-weight="bold">③ 좌표 1 탐색 후</text>

  <!-- 세 단계를 가르는 세로선 -->
  <g stroke="#ddd" stroke-width="1">
    <line x1="210" y1="0" x2="210" y2="240"/>
    <line x1="415" y1="0" x2="415" y2="240"/>
  </g>

  <!-- ─────────── ① 초기 ─────────── -->
  <!-- PQ 상자 -->
  <rect x="40" y="50" width="120" height="100" fill="#f7f7ff" stroke="#5b5bff" stroke-width="2" rx="6"/>
  <text x="100" y="70" font-size="12" text-anchor="middle" fill="#5b5bff">Priority&nbsp;Queue</text>
  <!-- 요소 (0,0) -->
  <rect x="55" y="86" width="90" height="28" fill="#dfe3ff" rx="4"/>
  <text x="100" y="106" font-size="12" text-anchor="middle">(0, 0)</text>

  <!-- dist 설명 -->
  <text x="55" y="170" font-size="12">dist[0] = 0</text>
  <text x="55" y="187" font-size="12">나머지는 INF</text>

  <!-- ─────────── ② 좌표 0 탐색 후 ─────────── -->
  <!-- PQ 상자 -->
  <rect x="235" y="50" width="120" height="100" fill="#f7fff7" stroke="#2c9d2c" stroke-width="2" rx="6"/>
  <text x="295" y="70" font-size="12" text-anchor="middle" fill="#2c9d2c">Priority&nbsp;Queue</text>
  <!-- 요소 (1,1) -->
  <rect x="250" y="86" width="90" height="28" fill="#c7f3c7" rx="4"/>
  <text x="295" y="106" font-size="12" text-anchor="middle">(1, 1)</text>
  <!-- 요소 (50,10) -->
  <rect x="250" y="118" width="90" height="28" fill="#c7f3c7" rx="4"/>
  <text x="295" y="138" font-size="12" text-anchor="middle">(50, 10)</text>

  <!-- dist 변화 표기 -->
  <text x="250" y="170" font-size="12">dist[1] = 1</text>
  <text x="250" y="187" font-size="12">dist[50] = 10</text>

  <!-- 화살표 -->
  <defs>
    <marker id="arrow" markerWidth="7" markerHeight="7" refX="6" refY="3.5" orient="auto">
      <path d="M0,0 L7,3.5 L0,7 Z" fill="#888"/>
    </marker>
  </defs>
  <path d="M160,100 C190,100 190,100 235,100" fill="none" stroke="#888" stroke-width="1.5" marker-end="url(#arrow)"/>

  <!-- ─────────── ③ 좌표 1 탐색 후 ─────────── -->
  <!-- PQ 상자 -->
  <rect x="440" y="50" width="120" height="100" fill="#fff7f7" stroke="#d33" stroke-width="2" rx="6"/>
  <text x="500" y="70" font-size="12" text-anchor="middle" fill="#d33">Priority&nbsp;Queue</text>
  <!-- 요소 (2,2) -->
  <rect x="455" y="86" width="90" height="28" fill="#ffdede" rx="4"/>
  <text x="500" y="106" font-size="12" text-anchor="middle">(2, 2)</text>
  <!-- 요소 (50,10) -->
  <rect x="455" y="118" width="90" height="28" fill="#ffdede" rx="4"/>
  <text x="500" y="138" font-size="12" text-anchor="middle">(50, 10)</text>

  <!-- dist 변화 표기 -->
  <text x="455" y="170" font-size="12">dist[2] = 2</text>

  <!-- 화살표 -->
  <path d="M355,100 C385,100 385,100 430,100" fill="none" stroke="#888" stroke-width="1.5" marker-end="url(#arrow)"/>

</svg>

즉 이와 같은 방식으로 우선순위 큐에서 가장 비용이 작은 상태부터 꺼내며, 목적지 D까지 최단거리를 찾아간다.

5️⃣ 데이터 흐름 (예제 1 : D = 150)

PQ pop 1 ㎞ 직진 enqueue 지름길 enqueue dist[] 최신값 비고

(0,0)	(1,1)	(50,10), (50,20)	dist[1]=1, dist[50]=10
(1,1)	(2,2)	–	dist[2]=2
…	…	–	…
(49,49)	(50,50)	–	갱신 안 됨 (이미 10)
(50,10)	(51,11)	(100,20)	dist[51]=11, dist[100]=20
…	…	…	…
(100,20)	(101,21)	–	dist[101]=21
…	…	…	…
(149,69)	(150,70)	–	dist[150]=70

좌표 0이 큐에서 빠지면
- 직진 1 ㎞ → (1,1)
- 지름길 0→50 (10)·(20) 두 개 → (50,10), (50,20)
비용 10짜리 (50,10) 이 가장 싸므로 먼저 확정
⇒ 지름길을 탄 효과가 반영된다.
이후 1 ㎞ 직진으로 BFS 처럼 뻗어가며 70 이라는 최단 거리가 완성된다.

지름길이 하나도 없더라도 직진 간선을 매 루프마다 “즉석으로” 넣어 주기 때문에 큐는 (0,0) → (1,1) → (2,2) → … → (D,D) 까지 자연스럽게 전달된다. 그리고 dist[D] 가 ‘직선으로만 달린 값’ 으로 무조건 채워진다.

이런 의문이 들 수 있다. 만약에 “지름길이 부족하면 초기화가 안 되지 않을까?”

결론부터 말하면, 지름길이 0 개라도 초기화가 안 될 일은 없다. 왜냐하면 직진 1 ㎞ 간선을 우리가 ‘루프 안에서’ 매번 즉석으로 만들어 PQ에 넣기 때문이다.

큐가 비는 순간은 언제?
(0,0) → (1,1) → (2,2) → … → (D,D) 까지 D + 1 개의 직진 상태가
차례로 꺼내지고 나서야 비게 된다.
dist 갱신은 어디서?
x = k 단계에서 dist[k+1] = dist[k] + 1 로 반드시 한 칸 앞 좌표를
갱신해 PQ에 다시 넣는다.
→ 결국 dist[D] = D 로 채워진다.

시뮬레이션 (D = 3, 지름길 없음) PQ pop 직진 enqueue dist[]

(0,0)	(1,1)	[0,1,∞,∞]
(1,1)	(2,2)	[0,1,2,∞]
(2,2)	(3,3)	[0,1,2,3]
(3,3)	–	끝

따라서 “지름길이 부족해서 dist[D] 가 영원히 INF로 남는다” 같은 상황은 애초에 발생할 수 없다. 지름길이 있으면 더 좋은 값으로 덮어쓰고, 없으면 직선 값 그대로 남는다는 안전한 구조가 보장된다.

🚀 최종 제출 코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {


	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int n = parseInt(stringTokenizer.nextToken());
		int D = parseInt(stringTokenizer.nextToken());

		List<Node> list = new ArrayList<>();
		while (n-- > 0) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int a = parseInt(stringTokenizer.nextToken());
			int b = parseInt(stringTokenizer.nextToken());
			int c = parseInt(stringTokenizer.nextToken());
			if(c < b-a && b <= D){
				list.add(new Node(a, b, c));
			}
		}

		List<List<Node>> graph = new ArrayList<>();
		for (int i = 0; i <= D; i++) {
			graph.add(new ArrayList<>());
		}

		for (Node node : list) {
			int start = node.start;
			int end = node.end;
			int d = node.cost;

			graph.get(start).add(new Node(start, end, d));
		}

		int[] dist = new int[D + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[0] = 0;

		PriorityQueue<State> pq = new PriorityQueue<>();
		pq.offer(new State(0, 0));

		while (!pq.isEmpty()) {
			State current = pq.poll();
			int currentX  = current.x;
			int currentCost = current.cost;
			if (currentCost > dist[currentX]){
				continue;
			}

			// 1km씩 전진
			if (도착지점까지도달하지못했고(currentX, D) && 더짧은거리인가(currentCost + 1, dist[currentX + 1])) {
				dist[currentX + 1] = currentCost + 1;
				pq.offer(new State(currentX + 1, dist[currentX + 1]));
			}

			// 지름길
			for (Node 지름길 : graph.get(currentX)) {
				if (더짧은거리인가(currentCost + 지름길.cost, dist[지름길.end])) {
					dist[지름길.end] = currentCost + 지름길.cost;
					pq.offer(new State(지름길.end, dist[지름길.end]));
				}
			}
		}

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

	}

	private static boolean 더짧은거리인가(int 후보거리, int 현재최단) {
		return 후보거리 < 현재최단;
	}

	private static boolean 도착지점까지도달하지못했고(int x, int D) {
		return x + 1 <= D;
	}

	public static class State implements Comparable<State> {
		int x;   // 1차원 평면에서 현재 위치 (0 ~ D)
		int cost;  // 출발점(0)에서 pos까지의 누적 거리

		State(int x, int cost) {
			this.x = x;
			this.cost = cost;
		}

		@Override
		public int compareTo(State o) {
			return Integer.compare(this.cost, o.cost);
		}
	}



	public static class Node {
		int start;
		int end;
		int cost;

		public Node(int x, int y, int cost) {
			this.start = x;
			this.end = y;
			this.cost = cost;
		}
	}

}

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 백준' 카테고리의 다른 글

[BOJ 백준] 18110 solved.ac (자바 풀이, 계수 정렬) (0)	2025.06.03
[BOJ 백준] 1759 암호만들기 (백트래킹 자바 풀이) (0)	2025.05.25
[BOJ] 백준 4195 친구 네트워크 (유니온 파인드 최적화 자바 풀이) (0)	2025.05.04
백준 5639 이진 검색 트리 (JAVA 자바 풀이) (0)	2024.11.23
[백준] 기념품 (자바 풀이) (4)	2024.10.12

르네의 영속성 컨텍스트

[BOJ 백준] 지름길 (자바 풀이, 그리디, 다익스트라)

📌 문제

⚔ 제한 사항

입력

출력

예시

👀 문제 해석

🔎 접근

💡 풀이 코드

1️⃣ 데이터 입력과 전처리

2️⃣ 그래프 구성

3️⃣ 거리 배열과 PQ 초기화

4️⃣ 다익스트라 알고리즘의 핵심 반복

5️⃣ 데이터 흐름 (예제 1 : D = 150)

🚀 최종 제출 코드

'알고리즘 > 백준' 카테고리의 다른 글

티스토리툴바

[BOJ 백준] 지름길 (자바 풀이, 그리디, 다익스트라)

📌 문제

⚔ 제한 사항

입력

출력

예시

👀 문제 해석

🔎 접근

💡 풀이 코드

1️⃣ 데이터 입력과 전처리

2️⃣ 그래프 구성

3️⃣ 거리 배열과 PQ 초기화

4️⃣ 다익스트라 알고리즘의 핵심 반복

5️⃣ 데이터 흐름 (예제 1 : D = 150)

🚀 최종 제출 코드

'알고리즘 > 백준' 카테고리의 다른 글

관련글

티스토리툴바