글 읽기 - 위상정렬을 이용한 풀이 58% 틀렸습니다가 뜨네요 ㅠㅠ

allen246 2년 전 1

어느 부분이 문제일까요? 혼자서 5~6번 만들어서 돌려봐도, 질문게시판에 있는 반례들도 다 맞는데... 조언 부탁드립니다!

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

    fun main() {
        val br = BufferedReader(InputStreamReader(System.`in`))
        val bw = BufferedWriter(OutputStreamWriter(System.`out`))
        val t = br.readLine().toInt()
        repeat(t) {
            val (n, k) = br.readLine().split(" ").map { it.toInt() }
            val incoming = Array(n + 1) { mutableListOf<Int>() }
            val outgoing = Array(n + 1) { mutableListOf<Int>() }
            val visited = BooleanArray(n + 1)
            val costs = br.readLine().split(" ").map { it.toLong() }.toMutableList()
            val dp = LongArray(n + 1)
            costs.add(0, 0)
            for (i in 0 until k) {
                val (x, y) = br.readLine().split(" ").map { it.toInt() }
                incoming[y].add(x)
                outgoing[x].add(y)
            }
            val finish = br.readLine().toInt()
            val queue: Queue<Pair<Int, Int>> = LinkedList()
            for (i in 1..n) {
                if (incoming[i].isEmpty()) {
                    queue.offer(Pair(i, 1))
                    visited[i] = true
                    dp[1] = maxOf(dp[1], costs[i])
                }
            }
            var lastCount = 0
            while (queue.isNotEmpty()) {
                val (node, count) = queue.poll()
                lastCount = count
                if (node == finish) break
                dp[count] = maxOf(dp[count], costs[node])
                for (otherNode in outgoing[node]) {
                    incoming[otherNode].remove(node)
                }
                for (i in 1..n) {
                    if (visited[i]) continue
                    if (incoming[i].isEmpty()) {
                        visited[i] = true
                        queue.offer(Pair(i, count + 1))
                    }
                }
            }
            var answer = 0L
            for (i in 1 until lastCount) answer += dp[i]
            answer += costs[finish]
            bw.write("$answer\n")
        }
        br.close()
        bw.close()
    }

veonico 2년 전 17

제출기록을 확인해봤는데 최종적으로는 문제를 해결하셨군요 축하드립니다.

제가 코틀린을 몰라서 본 코드를 이해하진 못했지만, 혹시 저와 같은 문제를 가지고 계신 분들이 계실까 글을 남겨봅니다.

저 역시 58%에서 틀렸는데요. 제가 틀린 이유는 "네트워크가 여러 개 존재하는 경우"를 고려하지 못해서입니다.

해당 반례입니다.

1
10 5
1 2 3 4 5 6 7 8 9 10
1 6
2 7
3 8
4 9
5 10
6

본 예시에서는 네트워크가 총 다섯 개 존재합니다.

위상 정렬 알고리즘 상 1번부터 5번 건물을 다 짓고 난 후에 6번 건물이 지어질 것입니다.

그러나 6번 건물을 짓기 위해서는 1번 건물만 지으면 되기 때문에 총 필요 시간은 (1+6) = 7초입니다.

그러나 6번 건물을 짓기 전에 1~5번 건물을 모두 지었기 때문에 6번 건물을 짓기 전 시간을 5초(1번 ~ 5번 건물을 짓는 시간의 최대값)이라고 가정하였고

결과적으로 11초 (5+6)가 걸렸다고 판단했네요.

혹시 58%에서 문제가 생긴 분들은 해당 반례를 고려해보는 것도 좋을 것 같습니다.

감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.