[백준/JAVA] 1446번: 지름길

📖 문제

1446번: 지름길

 

 

 

💡  풀이 방식

• 다익스트라 

필요 자료구조
- 지름길 정보 저장할 Road 객체 (지름길 시작 위치, 지름길 도착 위치, 지름길 길이)
- 지름길 객체 정보 저장할 Road형 배열
- 최단 거리 저장할 int형 배열

 

. (시작점,도착점,거리)를 저장하는 Road를 생성한다.

. Road형 배열에 객체 정보를 저장한다.

. 0부터 다익스트라를 진행한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int result = 0;
    
    static int N, D;
    static Road[] graph;
    static int[] dist; // 최단 거리 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken()); // 지름길 수
        D = Integer.parseInt(st.nextToken()); // 고속도로 길이
        
        dist = new int[D + 1];
        for(int i = 0 ; i < dist.length ; i++) {
            dist[i] = i;
        }
        
        graph = new Road[N];
        
        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 v = Integer.parseInt(st.nextToken()); // 지름길 길이
            
            graph[i] = new Road(s, e, v);
        }
        
        dijkstra(0);
        System.out.println(dist[D]);
    }
    
    private static void dijkstra(int start) {
        PriorityQueue<Road> pq = new PriorityQueue<>();
        pq.offer(new Road(start, 0, 0));
        
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Road cur = pq.poll();
            int nowPos = cur.e; // 현재 위치
            
            // 현재 위치에서 도달 가능한 도로들 확인
            for(Road r : graph) { 
                if(r.s >= nowPos) { // 시작 위치가 현재 위치보다 뒤쪽에 있을 때
                    if(r.e > D) continue; // 고속도로 벗어나면 pass
                                        
                    if(dist[r.e] > dist[nowPos] + r.v + (r.s - nowPos)) { // 🔔 최단 거리 갱신
                        dist[r.e] = dist[nowPos] + r.v + (r.s - nowPos);
                        pq.offer(new Road(nowPos, r.e, dist[r.e]));
                    }                    
                }
            }
            
            dist[D] = Math.min(dist[nowPos] + D - nowPos, dist[D]); // 🔔 현재 위치에서 D까지의 거리 고려해 최단 거리 갱신
        }
    }
}
 
class Road implements Comparable<Road> {
    int s, e, v;
    
    public Road(int s, int e, int v) {
        this.s = s;
        this.e = e;
        this.v = v;
    }
 
    // 비용 기준 오름차순 정렬
    @Override
    public int compareTo(Road r) {
        return this.v - r.v;
    }
}

 

 

 

 

 

➕ 다른 풀이 방식

객체를 List로 받고 정렬 부분 좀 다르게 하신 거

[최단경로] 백준 1446번 지름길 자바 (Java)

ArrayList<Road> graph = new ArrayList<>();

.
.
.

Collections.sort(graph, new Comparator<Road>() {
	public int compareTo(Road r1, Road r2) {
    	if(o1.s == o2.s)
        	return Integer.compare(o1.e, o2.e);
        return Integer.compareR(o1.s, o2.s);
    }
});

 

 

HashMap + Top-Down DP도 가능하다고 한다.

[ BOJ ][JAVA][1446] 지름길

 

 

DFS 풀이도 있다

백준 1446[자바] java 지름길

---

💦 어려웠던 점

다? 복습 2048번 해야 함,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[ BOJ ][JAVA][1446] 지름길

 

[최단경로] 백준 1446번 지름길 자바 (Java)