[ 백준 1005 ] - ACM Craft (Kotlin)

1005번: ACM Craft

 

문제 이해 & 기본 개념

• 각 건물의 소요 시간과 선행 관계가 주어질 때, 특정 건물을 짓기까지 걸리는 최소 시간을 구하는 문제

---

최종 풀이

• 기본 위상 정렬 문제에다가 각 건물의 위치에서의 최대 시간(이전 건물의 건설이 모두 끝나야하므로 최대)만 계산 해주면 된다.

---

 

소스 코드

import java.util.*
import kotlin.math.max

fun topologySort(
    n:Int,
    last:Int,
    adj:Array<ArrayList<Int>>,
    time:Array<Int>,
    dis:Array<Int>
): Int{
    val queue = LinkedList<Int>()
    val dp = Array(n){0}

    dis.forEachIndexed { idx, i ->
        if(i == 0){
        	// 최종 건물을 바로 지을 수 있으면 리턴
            if(idx == last) return time[idx]

            queue.add(idx)
            dp[idx] = time[idx]
        }
    }

    repeat(n){
        val cur = queue.poll()
        if(cur == last) return dp[cur]

        adj[cur].forEach { next ->
        	// 현재 위치의 최대 시간 + 다음 건물의 시간으로 다음 건물의 dp 값을 갱신
            dp[next] = max(dp[next], time[next] + dp[cur])
            if(--dis[next] == 0) {
                queue.add(next)
            }
        }
    }

    return 0
}

fun main(){
    val test = readln().toInt()

    repeat(test){
        // n: 건물 개수
        // k: 건설 순서 규칙
        val (n, k) = readln().split(" ").map { it.toInt() }

        val adj = Array<ArrayList<Int>>(n){ arrayListOf() } // 인접 리스트
        val time = Array(n){0} // 건설 시간
        val dis = Array(n){0}

        readln().split(" ").forEachIndexed { i, c ->
            time[i] = c.toInt()
        }

        repeat(k){
            val(n1, n2) = readln().split(" ").map { it.toInt()-1 }
            adj[n1].add(n2)
            dis[n2]++
        }

        // last: 목표 건물
        val last = readln().toInt()-1
        println(topologySort(n, last, adj, time, dis))
    }
}

 

 

 

#백준 #BOJ #java #kotlin #자바 #코틀린 #알고리즘