백준 게임개발 (Python/Go)

문제 링크: www.acmicpc.net/problem/1516

 

위상 정렬 문제입니다. 그런데 최소 시간을 알아내야 하기 때문에 위상정렬 + heap을 사용하여 풀어야 합니다.

아래는 파이썬 코드입니다.

import heapq
from collections import defaultdict
 
n = int(input())
degree = [0] * (n+1)  # degree[1] = 2 이라면 1번 건물을 짓기 위해 먼저 지어져야 하는 건물이 2개라는 뜻
time = [0] * (n+1)  # 각 건물 짓는데 걸리는 시간
graph = defaultdict(list)  # graph[1] = [2,3]이라면 건물2, 건물3을 짓기위해 건물1이 필요하단 뜻
 
for i in range(1, n+1):
    info = list(map(int, input().split()))
    time[i] = info[0]
    for j in range(1, len(info)):
        if info[j] == -1:
            break
 
        graph[info[j]].append(i)
        degree[i] += 1  # 먼저 지어야 되는 건물이 있을 때마다 1씩 증가시킴
 
 
heap = []  # 최소시간이므로 heap 사용
for i in range(1, n+1):
    if degree[i] == 0:
        heapq.heappush(heap, (time[i], i))
 
answer = defaultdict(int)
while heap:
    cur_t, cur_struct = heapq.heappop(heap)
    if cur_struct not in answer:
        answer[cur_struct] = cur_t
        for next_struct in graph[cur_struct]:
            degree[next_struct] -= 1
            if degree[next_struct] == 0:
                tot_t = cur_t + time[next_struct]  # 건물짓는데 걸리는 총 시간
                heapq.heappush(heap, (tot_t, next_struct))
 
 
for i in range(1, n+1):
    print(answer[i])
 
 

 

아래는 Go코드입니다.

package main
 
import (
    "bufio"
    "container/heap"
    "fmt"
    "os"
    "strconv"
)
 
type Item struct {
    time int
    node int
}
 
type PriorityQueue []*Item
 
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].time < pq[j].time
}
 
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}
 
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    *pq = old[0 : n-1]
    return item
}
 
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}
 
func main() {
    var n int
    fmt.Scanln(&n)
 
    degree := make([]int, n+1)  // degree[1] = 2 이라면 1번 건물을 짓기 위해 먼저 지어져야 하는 건물이 2개라는 뜻
    time := make([]int, n+1) // 각 건물 짓는데 걸리는 시간
    graph := make(map[int][]int)  // graph[1] = [2,3]이라면 건물2, 건물3을 짓기위해 건물1이 필요하단 뜻
 
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    for i:=1; i<=n; i++ {
        cnt := 0
        for {
            scanner.Scan()
            num, _ := strconv.Atoi(scanner.Text())
            if num == -1 {
                break
            }
 
            if cnt == 0 {
                time[i] = num
            } else {
                graph[num] = append(graph[num], i)
                degree[i] += 1
            }
            cnt += 1
        }
    }
 
    pq := PriorityQueue{}  // 최소시간이므로 heap 구조 사용
    for i:=1; i<=n; i++ {  // 먼저 지어야할 건물이 없는 건물부터 pq에 넣음
        if degree[i] == 0 {
            heap.Push(&pq, &Item{time[i], i})
        }
    }
 
    answer := make(map[int]int)
    for {
        if len(pq) == 0 {
            break
        }
 
        item := heap.Pop(&pq).(*Item)
        curTime, curStruct := item.time, item.node
        if _, ok := answer[curStruct]; !ok {  // answer에 없으면 추가
            answer[curStruct] = curTime
            for _, nextStruct := range graph[curStruct] {
                degree[nextStruct] -= 1
                if degree[nextStruct] == 0 {
                    totTime := curTime + time[nextStruct]  // 건물 짓는데 걸리는 총 시간
                    heap.Push(&pq, &Item{totTime, nextStruct})
                }
            }
        }
    }
 
    for i:=1 ;i<=n; i++ {
        fmt.Println(answer[i])
    }
}

 

파이썬은 188ms, Go는 40ms가 나옵니다.