백준 1753 풀이
https://www.acmicpc.net/problem/1753
최단경로
주어진 그래프에서 최단경로를 구하는 문제이다.
최단 경로를 구하는 데 있어 여러가지 방법이 있지만 이번 문제에서는 음의 가중치가 없고, 시작점이 주어졌기 때문에 다익스트라 알고리즘을 사용해서 풀이했다.
풀이
최단 거리를 구할 때 방법으로 배열을 이용하는 방법과 우선 순위 큐를 이용하여 구하는 방법 2가지가 있다.
배열을 이용하여 최단거리를 구한다면 연결된 모든 정점을 탐색해야 하기때문에 우선 순위 큐를 이용하여 구현하는 것보다 시간이 오래 걸린다.
따라서 우선 순위 큐를 이용해서 다익스트라 알고리즘을 구현했다.
우선 순위 큐에 간선을 넣을 때 주의할 점이 있다.
우선 순위 큐에 삽입해 정렬을 할 때 기준값은 weight 값으로 오름차순으로 정렬이 된다.
따라서 큐에 삽입할 때 목적지 좌표와 함께 가중치는 해당 목적지까지 가는데 든 가중치의 합이 들어가야 한다.
import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static boolean[][] visit;
static int n, m;
static int ans = 0;
static int[] chess;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] nums = br.readLine().split(" ");
n = Integer.parseInt(nums[0]);
m = Integer.parseInt(nums[1]);
int k = Integer.parseInt(br.readLine());
ArrayList<Pair>[] graph = new ArrayList[n + 1];
PriorityQueue<Pair> queue = new PriorityQueue<>();
for (int i = 0; i <= n; i++)
graph[i] = new ArrayList<>();
int[] distance = new int[n + 1];
boolean[] visited = new boolean[n + 1];
for (int i = 0; i < m; i++) {
String[] line = br.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
graph[x].add(new Pair(y, w));
}
for (int i = 1; i <= n; i++) {
if (i == k)
distance[i] = 0;
else
distance[i] = Integer.MAX_VALUE;
}
queue.offer(new Pair(k, 0));
while (!queue.isEmpty()) {
Pair p = queue.poll();
int y = p.y;
if (visited[y])
continue;
else
visited[y] = true;
for (Pair next : graph[y]) {
if (distance[next.y] >= distance[y] + next.w) {
distance[next.y] = distance[y] + next.w;
queue.offer(new Pair(next.y, distance[next.y]));
}
}
}
for(int i = 1;i<=n;i++) {
if(distance[i] != Integer.MAX_VALUE)
System.out.println(distance[i]);
else
System.out.println("INF");
}
//bw.write(ans + "\n");
br.close();
bw.close();
}
}
class Pair implements Comparable<Pair> {
public int y;
public int w;
public Pair(int y, int w) {
this.y = y;
this.w = w;
}
@Override
public int compareTo(Pair o) {
return Integer.compare(this.w, o.w);
}
}
Author And Source
이 문제에 관하여(백준 1753 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-1753-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)