HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • front-end
  • Database
  • 프로그래머스C++
  • 백준C++
  • 백준
  • 개발자
  • Baekjoon Online Judge
  • 코딩
  • 백엔드
  • 데이터베이스
  • 알고스팟
  • 백준Python
  • Algospot
  • 백준Go
  • 프로그래밍
  • 프로그래머스Python
  • 프로그래머스
  • back-end
  • programmers
  • 알고스팟Python

최근 댓글

인기 글

hELLO
HelloMinchan
Deprecated

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

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

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

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)
 
 
T = 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])

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[programmers] 프로그래머스 문자열 압축(Python)  (0) 2020.06.17
[programmers] 프로그래머스 주식가격(Python)  (0) 2020.06.17
[Baekjoon Online Judge] 백준 2252번 줄 세우기(Python)  (0) 2020.06.16
[Baekjoon Online Judge] 백준 2887번 행성 터널(Python)  (0) 2020.06.16
[Baekjoon Online Judge] 백준 1647번 도시 분할 계획(Python)  (0) 2020.06.16
  • [Baekjoon Online Judge] 백준 1005번 ACM Craft
  • (Python)
  • 백준 1005번 ACM Craft
'Deprecated' 카테고리의 다른 글
  • [programmers] 프로그래머스 문자열 압축(Python)
  • [programmers] 프로그래머스 주식가격(Python)
  • [Baekjoon Online Judge] 백준 2252번 줄 세우기(Python)
  • [Baekjoon Online Judge] 백준 2887번 행성 터널(Python)
HelloMinchan
HelloMinchan
Though you should not fear failure, You should do your very best to avoid it.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.