[백준] 1753번 : 최단경로(다익스트라) - 자바[Java]

1753번: 최단경로

풀이

그래프 최단 경로를 구하는 다익스트라 알고리즘을 사용하여 푸는 문제다.

인접리스트, PriorityQueue, 각 정점까지의 최단 경로를 저장하는 dis 배열을 사용하여 풀었으며 자세한 풀이는 이전에 풀었던 문제와 같기 때문에 설명은 생략하겠다.

[프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java]

[프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java]

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static class Edge implements Comparable<Edge>{
        public int vertex;
        public int cost;

        Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
        @Override
        public int compareTo(Edge ob){
            return this.cost-ob.cost;
        }
    }

    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 m = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph.get(a).add(new Edge(b, c));
        }

        int[] dis = dijkstra(graph, start, n);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (dis[i] == Integer.MAX_VALUE)
                sb.append("INF\n");
            else
                sb.append(dis[i]+"\n");
        }

        System.out.println(sb);
    }

    static int[] dijkstra(ArrayList<ArrayList<Edge>> graph, int start, int n) {
        int[] dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int vertex = cur.vertex;
            int cost = cur.cost;

            if (dis[vertex] < cost) continue;

            for (Edge e : graph.get(vertex)) {
                if (dis[e.vertex] > cost + e.cost) {
                    dis[e.vertex] = cost + e.cost;
                    pq.add(new Edge(e.vertex, dis[e.vertex]));
                }
            }
        }

        return dis;
    }

}

 

2023.08.01 코드

import java.io.*;
import java.util.*;

public class Main {
	
	static class Edge implements Comparable<Edge> {
		int v;
		int cost;
		
		public Edge(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
	
	static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
	static int[] dist; // 최소거리
	static int INF = 100000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		
		// 그래프 초기화
		for (int i = 0; i <= v; i++) {
			graph.add(new ArrayList<>());
		}
		
		// 입력
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			graph.get(a).add(new Edge(b, c));
		}
		
		dijkstra(v, start);
		
		// 출력
		for (int i = 1; i <= v; i++) {
			if (dist[i] == INF) sb.append("INF\n");
			else sb.append(dist[i] + "\n");
		}
		bw.write(sb.toString());
		bw.flush();
		br.close();
		bw.close();
	}
	
	static void dijkstra(int v, int start) {
		// 0. 최소거리 배열 초기화
		// dist[i]  : 출발점 ~ i까지가는데 필요한 최소비용
		dist = new int[v+1];
		for (int i = 1; i <= v; i++) {
			dist[i] = INF;
		}
		
		// 1. 출발지 비용은 0으로 하고 출발지를 PQ에 넣고 시작
		dist[start] = 0;
		
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.add(new Edge(start, 0));
		
		// 2. 최소 힙에서 맨 위에 있는 정점 꺼냄
		while (!pq.isEmpty()) {
			Edge cur = pq.poll(); // cost: 누적비용
			
			// 1) 누적 비용 > dist[] 이면 더 큰 가중치로 도착한 것이므로 continue
			if (cur.cost > dist[cur.v]) continue;
			
			// 2) 현재 위치에 연결된 간선 탐색
			for (Edge next: graph.get(cur.v)) {
				// dist[next.target]  비교 now.cost(누적비용) + next.cost(간선비용)
				// 3) cost가 더 작을때만 갱신하고 PQ에 넣기
				if (dist[next.v] > cur.cost + next.cost) {
					dist[next.v] = cur.cost + next.cost;
					pq.add(new Edge(next.v, dist[next.v]));
				}
			}
		}
	}
	
}