백준 - 10282 해킹(Kotlin, 다익스트라)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/10282

 

[문제 설명]

컴퓨터 바이러스가 모두 퍼질 때까지 걸리는 시간을 구하시오.

 

[접근 방법]

문제가 딱 봤을 때, 다익스트라라는 느낌을 받지 못했다.

따라서, 시간을 기준으로 정렬하는 힙을 구현하고 계속 그래프 탐색을 하면 된다고 생각했다.

또한, 중간에 왔던 좌표를 또 올 수 있으므로 dp로 지금 좌표에 오는 데까지 걸린 시간을 기록하였다.

 

정리하고 코드를 작성하고 보니 다익스트라 코드가 자연스럽게 나왔다.

 

그런데! 여기서 두 가지 실수를 했다.

첫 번째 정렬 실수였다.

// 수정 전 코드
data class Node(val destination: Int, val time: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return if (time <= other.time) {
            1
        } else {
            -1
        }
    }
}

// 수정 후 코드
data class Node(val destination: Int, val time: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return time - other.time
    }
}

나는 평소에 정렬을 구현할 때, 단순히 return a - b 이런 식으로 정렬하고는 했다.

그런데 이번에는 무슨 일인지 단순하게 if-else문으로 구현했는데 이게 문제였다.

Comparator를 구현할 때는 같을 경우 0을 리턴하도록 설정해야 한다.

자세한 이유는 밑에 링크에 들어가서 볼 수 있다.

https://stackoverflow.com/questions/58267950/why-we-need-to-return-0-when-comparator-compare-become-equal

 

두 번째 실수는 다익스트라 구현에서 실수를 했다.

이전까지의 최소 거리에서 다음 거리를 더해야 하는데, 이를 이용하지 않고 바로 이전 거리에서 현재 거리를 더했다.

// 수정전 코드 : 이전까지의 거리가 아닌 현재 거리에서 다음 거리를 더해줌.
if (dp[nextNode.destination] > cNode.time + nextNode.time) {
    dp[nextNode.destination] = cNode.time + nextNode.time
    pq.offer(Node(nextNode.destination, cNode.time + nextNode.time))
    cntOfInfectedPc--
}

// 수정 후 코드 : 이전까지의 기록한 최소 거리를 기준으로 다음 거리를 더해줌.
if (dp[nextNode.destination] > dp[cNode.destination] + nextNode.time) {
    dp[nextNode.destination] = dp[cNode.destination] + nextNode.time
    pq.offer(Node(nextNode.destination, dp[nextNode.destination]))
}

 

[수정 후 코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.PriorityQueue

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    // 테스트 케이스 개수
    val t = br.readLine().toInt()
    repeat(t) {
        // n : 컴퓨터의 개수, d : 의존성 개수, c : 시작 컴퓨터의 번호
        val (n, d, c) = br.readLine().split(" ").map { it.toInt() }
        // 지도
        val map = Array(n) { ArrayList<Node>() }

        repeat(d) {
            // b가 감염되면 a가 5초 후에 감염
            val (a, b, s) = br.readLine().split(" ").map { it.toInt() }
            map[b - 1].add(Node(a - 1, s))
        }

        val output = bfs(start = c - 1, map = map)
        val cntOfPc = output.first
        val time = output.second
        bw.write("$cntOfPc $time\n")
    }
    bw.flush()
}

fun bfs(start: Int, map: Array<ArrayList<Node>>): Pair<Int, Int> {
    var cntOfInfectedPc = 0
    var maxTime = 0
    // dp[a] = a까지 가는 데 드는 최소 시간.
    val dp = IntArray(map.size) { Int.MAX_VALUE }
    val visited = BooleanArray(map.size)
    val pq = PriorityQueue<Node>()

    pq.offer(Node(start, 0))
    dp[start] = 0

    while (pq.isNotEmpty()) {
        // 현재 노드
        val cNode = pq.poll()

        if (!visited[cNode.destination]) {
            visited[cNode.destination] = true
            cntOfInfectedPc++
        }

        for (nextNode in map[cNode.destination]) {
            // if : 방문했던 노드여도 이번이 최소값이면 넣어주고 다시 조회해야함.
            if (dp[nextNode.destination] > dp[cNode.destination] + nextNode.time) {
                dp[nextNode.destination] = dp[cNode.destination] + nextNode.time
                pq.offer(Node(nextNode.destination, dp[nextNode.destination]))
            }
        }
    }

    dp.forEach {
        if (it != Int.MAX_VALUE) {
            maxTime = maxTime.coerceAtLeast(it)
        }
    }

    return cntOfInfectedPc to maxTime
}

data class Node(val destination: Int, val time: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return time - other.time
    }
}

다익스트라에 익숙했다면 문제를 차근차근 찾아볼 수 있었겠지만, 다익스트라에 익숙하지 않다보니 어디서 틀린지 굉장히 헷갈렸다.

따라서, 틀린 부분을 찾는데 상당히 시간이 걸렸다.

다음에는 Comparator를 구현할 때 1,0,-1을 모두 구현해주자!!