문제
백준 1753번
https://www.acmicpc.net/problem/1753
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
생각하기
이 문제는 다익스트라 알고리즘의 기초를 다루는 문제이다.
다익스트라 알고리즘은 쉽고 간략하게 설명하자면,
출발지에서 원하는 목적지까지 가중치를 기준으로 가장 낮은 값으로 갈 수 있는 길을 찾는 것이다.
가중치 없이 길이를 기준으로 해도 가장 빠른 길을 탐색하는 알고리즘이라고 할 수 있다.
그래프 탐색에서는 꼭 알고있어야 할 알고리즘 중 하나이다.
나도 이 문제를 통해서 다익스트라를 처음 접해봤다..
동작
static ArrayList<ArrayList<Node>> list;
static final int INF = Integer.MAX_VALUE / 16;
static int dist[];
static class Node implements Comparable<Node> {
int nodeNum;
int weight;
public Node(int nodeNum, int weight) {
this.nodeNum = nodeNum;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
} // End of Node class우선 다익스트라 알고리즘을 하기 위해서 필요한 바탕이 되는 부분이다.
인접리스트로 구현을 했기때문에 static 인접리스트 list를 만들었고
갈 수 없는 경로인 INF를 만들어주었다.
INF 가 Integer.MAX_VALUE / 16인 이유는 Integer의 최대값에서 연산을 할 경우, 혹시 모를 오버플로우를 대비하기위해서 값을 조금 줄이기 위해 16으로 나눴다.
16인 이유는 그냥 1234.. 와 가장 비슷한 숫자여서 했다 (큰 의미 없음)
그리고 가중치 값을 비교하여 갱신하기 위해 Comparable의 인터페이스를 가져와서
CompareTo를 사용해서 비교한다.
dist = new int[N + 1];
Arrays.fill(dist, INF);
list = new ArrayList<>();
for(int i=0; i<=N; i++) {
list.add(new ArrayList<>());
}
int start = Integer.parseInt(br.readLine());
while(M-->0) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list.get(x).add(new Node(y, w));
}이 부분은 거리 값을 담기위한 dist 배열 초기화와
인접행렬을 노드 숫자 만큼 생성하는 부분이다.
인접리스트는 그냥 인접행렬인 2차원 배열을
리스트로 만든 2차원 배열의 리스트형이라고 생각하면 된다.
각각 장단점이 있으니, 아래의 링크를 한번 읽어보길 바란다.
인접행렬과 인접리스트
PriorityQueue<Node> que = new PriorityQueue<Node>();
boolean check[] = new boolean[N + 1];
dist[start] = 0;
que.offer(new Node(start, 0));다익스트라 알고리즘은 BFS와 굉장히 비슷하다
Queue가 빌때까지 반복하는 방식이다.
차이점이라면 다익스트라는 우선순위 큐인 PriorityQueue를 사용한다는 점이다.
그리고 처음 문제에서 나온대로 시작점인 start부터 갈 수 있는 모든곳의 최단 값을 출력하는 문제이기 때문에 전체를 탐색한다.
자기자신은 갈 수 없음은 아니지만 비용이 없으므로 dist[start]의 값을 0으로 해준다.
while( !que.isEmpty() ) {
Node queNode = que.poll();
int startNum = queNode.nodeNum;
if( !check[startNum] ) {
check[startNum] = true;
for(Node node : list.get(startNum)) {
if( !check[node.nodeNum] && dist[node.nodeNum] > (dist[startNum] + node.weight) ) {
dist[node.nodeNum] = dist[startNum] + node.weight;
que.offer(new Node(node.nodeNum, dist[node.nodeNum]));
}
}
}이제 start부터 시작해서 갈 수 있는 모든 노드를 순회하며
que에 집어넣는는다.
check를 통해 각 노드를 방문했는지 하지 않았는지를 검사하고,
방문한적이 없는 노드를 우선으로 가중치 값을 계속 갱신하면서, 반복하면 답을 얻을 수 있다.
코드
Java
import java.util.*;
import java.io.*;
public class Main {
static ArrayList<ArrayList<Node>> list;
static final int INF = Integer.MAX_VALUE / 16;
static int dist[];
static class Node implements Comparable<Node> {
int nodeNum;
int weight;
public Node(int nodeNum, int weight) {
this.nodeNum = nodeNum;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
} // End of Node class
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
dist = new int[N + 1];
Arrays.fill(dist, INF);
list = new ArrayList<>();
for(int i=0; i<=N; i++) {
list.add(new ArrayList<>());
}
int start = Integer.parseInt(br.readLine());
while(M-->0) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list.get(x).add(new Node(y, w));
}
dijkstra(start, N);
for(int i=1; i<=N; i++) {
if(dist[i] == INF) {
sb.append("INF\n");
continue;
}
sb.append(dist[i]).append('\n');
}
System.out.println(sb);
} // End of main
static void dijkstra(int start, int N) {
PriorityQueue<Node> que = new PriorityQueue<Node>();
boolean check[] = new boolean[N + 1];
dist[start] = 0;
que.offer(new Node(start, 0));
while( !que.isEmpty() ) {
Node queNode = que.poll();
int startNum = queNode.nodeNum;
if( !check[startNum] ) {
check[startNum] = true;
for(Node node : list.get(startNum)) {
if( !check[node.nodeNum] && dist[node.nodeNum] > (dist[startNum] + node.weight) ) {
dist[node.nodeNum] = dist[startNum] + node.weight;
que.offer(new Node(node.nodeNum, dist[node.nodeNum]));
}
}
}
}
} // End of dijkstra
} // End of Main classKotlin
import java.util.*;
import java.io.*
private const val INF = Integer.MAX_VALUE / 14;
private var V = 0; private var E = 0; private var K = 0
private lateinit var list : MutableList<MutableList<Node>> // 인접리스트
private lateinit var dist : IntArray
private class Node(var nodeNum : Int, var weight : Int) : Comparable<Node> {
override fun compareTo(other: Node): Int {return weight - other.weight}
}
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.`out`))
val sb = StringBuilder()
var st = StringTokenizer(br.readLine())
V = st.nextToken().toInt() // 정점(노드)의 개수
E = st.nextToken().toInt() // 간선의 개수
K = br.readLine().toInt() // 출발 노드
dist = IntArray(V+1 , {INF})
list = ArrayList()
for(i in 0 until V+1) list.add(ArrayList())
for(i in 0 until E) {
st = StringTokenizer(br.readLine())
var start = st.nextToken().toInt()
var end = st.nextToken().toInt()
var w = st.nextToken().toInt()
list.get(start).add(Node(end, w));
}
dijkstra(K)
for(i in 1..V) {
if(dist[i] == INF) {
sb.append("INF").append('\n')
continue
}
sb.append(dist[i]).append('\n')
}
bw.write(sb.toString());bw.flush();bw.close()
} // End of main
private fun dijkstra(start : Int) {
val que = PriorityQueue<Node>()
val check = BooleanArray(V+1)
dist[start] = 0
que.offer(Node(start, 0))
while(!que.isEmpty()) {
var queNode = que.poll()
var startNum = queNode.nodeNum
if(check[startNum]) continue
check[startNum] = true
list.get(startNum).forEach {
if(!check[it.nodeNum] && dist[it.nodeNum] > (dist[startNum] + it.weight)) {
dist[it.nodeNum] = dist[startNum] + it.weight
que.offer(Node(it.nodeNum, dist[it.nodeNum]))
}
}
}
} // End of dijkstra