백준 11657번 타임머신 Kotlin

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

문제

---

생각하기

---

• SPFA 알고리즘

• 그래프

• 음수 가중치

동작

거리 갱신과 inQueue를 분리하는 이유

inQueue의 역할은 큐에 중복된 정점이 들어가는 것을 방지하는 목적
만약 이미 큐에 있는 정점의 거리가 갱신되었다고 해서 다시 큐에 넣게 되면, 불필요한 연산이 반복되고 심지어 무한 루프에 빠질 수도 있습니다.

결과

코드

---

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private lateinit var adjList: MutableList<MutableList<Edge>>
private const val INF = Long.MAX_VALUE
private data class Edge(val num: Int, val weight: Int)


fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val ret = SPFA()
    if (ret == null) {
        sb.append(-1)
    } else {
        for (i in 2..N) {
            if (ret[i] == INF) {
                sb.append(-1)
            } else {
                sb.append(ret[i])
            }
            sb.append('\n')
        }
    }

    return sb.toString()
} // End of solve()

private fun SPFA(): LongArray? {
    val que = ArrayDeque<Int>()
    val dist = LongArray(N + 1) { INF }
    val inQueue = BooleanArray(N + 1)
    val count = IntArray(N + 1)

    que.addLast(1)
    inQueue[1] = true
    dist[1] = 0
    count[1] = 1

    while (que.isNotEmpty()) {
        val cur = que.removeFirst()

        if (dist[cur] == INF) continue
        inQueue[cur] = false

        for (next in adjList[cur]) {

            if (dist[next.num] > dist[cur] + next.weight) {
                dist[next.num] = dist[cur] + next.weight // 갱신

                if (inQueue[next.num]) continue
                que.addLast(next.num)
                inQueue[next.num] = true
                count[next.num]++

                if (count[next.num] == N) {
                    return null
                }
            }
        }
    }

    return dist
} // End of SPFA()

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    adjList = mutableListOf()
    repeat(N + 1) {
        adjList.add(mutableListOf())
    }

    repeat(M) {
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()
        val c = st.nextToken().toInt()

        adjList[a].add(Edge(b, c))
    }
} // End of input()