백준 1916번
https://www.acmicpc.net/problem/1916

문제

---

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

생각하기

---

코틀린으로 처음푸는 다익스트라 알고리즘 문제였다.

다익스트라 알고리즘은 알고있어서 어렵지 않았지만, 인접리스트를 코틀린으로는 처음으로 만들어봐서 굉장히 까다로웠고, 처음으로 lateinit도 적용해봤고 여러모로 의미있는 코딩이었다

다익스트라 알고리즘을 통해서 가중치의 최소값을 구하기 위해서는 몇 가지의 특징이있는데,

1. 인접리스트를 사용
2. 우선순위 큐를 사용

이 2가지가 가장 중요하다고 생각할 수 있다.

인접리스트를 구현할 때 도 2가지로 나뉜는데, ArrayList와 배열 조합, ArrayList ArrayList 이렇게 2가지로 나뉜다.

나는 구현이 ArrayList ArrayList로 하는 인접리스트가 더 좋아서 개인적으로 이 방식으로 인접리스트를 구현했다.

어떤 것을 사용해도 상관은 없다.

동작

private lateinit var list: MutableList<MutableList<Node>>
private lateinit var dist: IntArray

    dist = IntArray(N+1){INF};
    // 노드의 개수 만큼 인접리스트 생성
    list = ArrayList()
    for(i in 0..N) {
        list.add(ArrayList())
    }

먼저 전역 변수로 인접리스트list 와 가중치값을 담을 배열 dist를 만들어준다.

초기화는 아래로 와서 N이 들어오고 난 후에 해주면된다.

list는 우리가 노드의 개수 만큼 만들어야 하기 때문에 0부터N까지의 개수 만큼 노드번호로 생성해준다.

    while( !que.isEmpty() ) {
        var queNode : Node = que.poll();
        var start_nodeNum = queNode.nodeNum;

        if( !visit[start_nodeNum] ) {
            visit[start_nodeNum] = true;

            list.get(start_nodeNum).forEach {

                if( !visit[it.nodeNum] && dist[it.nodeNum] > (dist[start_nodeNum] + it.weight)) {
                    dist[it.nodeNum] = dist[start_nodeNum] + it.weight
                    que.offer(Node(it.nodeNum, dist[it.nodeNum]))
                }

            }
        }

BFS와 흡사한 모습이다.
우선순위 큐가 빌어 있지 않으면 계속해서 반복해서 weight인 가중치값을 갱신한다.

또한 노드의 방문여부를 알기 위해서 visit배열도 만들어준다.

                if( !visit[it.nodeNum] && dist[it.nodeNum] > (dist[start_nodeNum] + it.weight)) {
                    dist[it.nodeNum] = dist[start_nodeNum] + it.weight
                    que.offer(Node(it.nodeNum, dist[it.nodeNum]))
                }

해당 코드가 방문하지 않은 노드의 가중치 값이 현재 있는 간선의 가중치 값과 기존의 가중치 값의 합이 최소이면 교환하는 코드이다.

코드

---

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

// 인접리스트 생성
private lateinit var list: MutableList<MutableList<Node>>
private lateinit var dist: IntArray
private const val INF = Integer.MAX_VALUE / 4 // 오버플로우 방지
private var N = 0;
private var M = 0;

private class Node(var nodeNum : Int, var weight: Int) : Comparable<Node> {
	// 우선순위 큐에서 가중치 비교를 위한 메소드 override
    override fun compareTo(other: Node): Int {
        return weight - other.weight;
    }
} // End of Node class

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`) )
    N = br.readLine().toInt()
    M = br.readLine().toInt()

    dist = IntArray(N+1){INF};
    // 노드의 개수 만큼 인접리스트 생성
    list = ArrayList()
    for(i in 0..N) {
        list.add(ArrayList())
    }

    for(i in 1..M) {
        var st = StringTokenizer(br.readLine());
        var start = st.nextToken().toInt()
        var end = st.nextToken().toInt()
        var weight = st.nextToken().toInt()
        list.get(start).add(Node(end, weight));
    }

    var st = StringTokenizer(br.readLine())
    val start = st.nextToken().toInt()
    val end = st.nextToken().toInt()

    println(dijkstra(start, end))

} // End of main

fun dijkstra(start : Int, end : Int) : Int {
    var que : PriorityQueue<Node> = PriorityQueue();
    var visit : BooleanArray = BooleanArray(N + 1);
    dist[start] = 0;
    que.offer(Node(start, 0))

    while( !que.isEmpty() ) {
        var queNode : Node = que.poll();
        var start_nodeNum = queNode.nodeNum;

        if( !visit[start_nodeNum] ) {
            visit[start_nodeNum] = true;

            list.get(start_nodeNum).forEach {

                if( !visit[it.nodeNum] && dist[it.nodeNum] > (dist[start_nodeNum] + it.weight)) {
                    dist[it.nodeNum] = dist[start_nodeNum] + it.weight
                    que.offer(Node(it.nodeNum, dist[it.nodeNum]))
                }

            }
        }
    }

    return dist[end];
} // End of dijkstras