백준 1753 - 최단경로

백준 1753 - 최단경로

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

22일전에 풀었던 문제이다. 다익스트라를 사용해서 푸는 문제이고 정점의 개수와 간선의 개수가 많기 때문에 시간초과에 주의해서 풀어야 하는 문제이다.

★ 풀이

문제에서 시작노드, 노드간 경로와 가중치(거리)가 주어지고 이것들을 이용하여 시작노드에서 다른 노드까지의 최단 거리 및 도달 가능성(불가능시 INF) 등을 출력하는 문제이다. 한 점에서 다른 모든 점까지의 거리를 구하는 문제이므로 다익스트라, 벨만포드, 플로이드 와샬 등으로 풀 수 있는 문제이다. 간단한 플로이드 와샬로 풀고 싶었지만 노드의 개수와 간선의 개수가 굉장히 많기 때문에 삼중포문을 이용해서 풀어버리면 바로 시간초과가 나올 것 같아서 그래도 활용해본 경험이 있는 다 익스트라를 활용하여 풀었다. (벨만 포드는 가중치가 음수가 있는 것도 아니고, 한번 밖에 써본 적이 없어서 제외했지만.. 나중에 다시 공부할 예정임).

다 익스트라 알고리즘을 사용할 때 우선순위 큐를 사용한 이유는 매순간 최선의 선택을 해야 그 순간에서 그 선택이 보장되고 나중에 불필요한 연산을 하지 않아도 되기 때문이다. 또 우선순위 큐 말고 일반 큐를 사용하고 반복문이나 다른 방법 등으로 최소값을 찾아서 하는 방법도 존재하긴 하지만 시간상 힙을 써서 하는게 더 효율적이기 때문에 우선순위큐를 사용했다.

★ 소스 코드

import java.io.*; import java.util.*; class Node implements Comparable{ int to; int dist; Node(int to, int dist){ this.to = to; this.dist = dist; } @Override public int compareTo(Node o) { return this.dist - o.dist; } } public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static ArrayList adj[]; static int ans[]; static int start,v; static int dist[]; static boolean visited[]; public static void main(String[] args) throws IOException { StringTokenizer st = new StringTokenizer(br.readLine()); int v = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); start = Integer.parseInt(br.readLine()); dist = new int[v + 1]; ans = new int[v + 1]; adj = new ArrayList[v + 1]; visited = new boolean[v + 1]; for(int i = 1; i<=v; i++) { adj[i] = new ArrayList<>(); } for(int i = 0; i

"); else bw.write(dist[i]+"

"); } bw.flush(); } static void solve() { PriorityQueue q = new PriorityQueue<>(); q.add(new Node(start,0)); while(!q.isEmpty()) { Node x = q.poll(); for(Node next : adj[x.to]) { if(dist[next.to] > dist[x.to] + next.dist) { dist[next.to] = dist[x.to] + next.dist; q.add(new Node(next.to,dist[next.to])); } } } } }

from http://sweet-smell.tistory.com/38 by ccl(A) rewrite - 2021-08-25 02:26:14