상세 컨텐츠

본문 제목

[Baekjoon Online Judge] 백준 1005번 ACM Craft(Python)

Problem Solving/Baekjoon Online Judge

by HelloMinchan 2020. 6. 16. 23:23

본문

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1005번 ACM Craft

(Python)

(글쓴날 : 2020.06.16)

 


* Baekjoon Online Judge, 백준 1005번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 1005번 ACM Craft


1) 문제

문제 링크 : https://www.acmicpc.net/problem/1005

 

1005번: ACM Craft

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부�

www.acmicpc.net


2) 풀이 과정

* 시간 복잡도 : O(E+V)

 

건물을 짓는 순서와 각 건물을 짓는데 걸리는 시간이 주어질 때, 특정 건물을 짓기까지 걸리는 최소 시간을 구하는 문제입니다.

 

저의 경우, 위상 정렬을 적용하였고, Python을 사용했습니다.

먼저 주어지는 정보들을 인접 리스트에 구현한 뒤, 위상 정렬을 적용해 건물을 짓는 테크트리를 찾아냈습니다.

위상 정렬을 수행하면서 찾은 테크트리 순서대로, 해당 건물을 짓기까지 가장 오래 걸린 시간을 기록해 나갔고, 최종적으로 건물 W를 짓는데 걸린 시간을 구해 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import deque
import sys
input = sys.stdin.readline
 
 
def topologicalSort():
    for _ in range(N):
        if not dq:
            return
 
        target = dq.popleft()
 
        for x in adjList[target]:
            sequence[x] = max(sequence[x], sequence[target] + D[x])
            indegree[x] -= 1
            
            if not indegree[x]:
                dq.append(x)
 
 
= int(input())
 
for _ in range(T):
    N, K = map(int, input().split())
    D = [0+ list(map(int, input().split()))
 
    sequence = [0* (N + 1)
    indegree = [0* (N + 1)
    adjList = [[] for _ in range(N + 1)]
 
    for _ in range(K):
        X, Y = map(int, input().split())
 
        indegree[Y] += 1
        adjList[X].append(Y)
    
    W = int(input())
 
    dq = deque()
    for i in range(1, N + 1):
        if not indegree[i]:
            sequence[i] = D[i]
            dq.append(i)
 
    topologicalSort()
 
    print(sequence[W])

 

관련글 더보기

댓글 영역