[백준]1005 ACM Craft(Python)

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

문제 접근

 

시도1. (실패)

어제와 정리한 위상정렬 함수를 변형해서 작성하였다.

1. 건물의 건설 시간을 담을 리스트를 인덱스에 대응시켜서 만든다.

2. 특정 건물(W)까지 짓는데 걸리는 시간을 total_cost라는 변수에 누적해서 결과로 출력한다.

=> 예제 1 출력 결과: 121 52

 

수정(성공)

 

코드

 

시도1 

from collections import deque
import sys

input = sys.stdin.readline


# 위상 정렬 함수
def topology_sort():
    result = [] # 결과를 담을 리스트
    q = deque()
    total_cost = 0

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입(1부터 v까지 체크)
    for i in range(1, K+1):
        if indegree[i] == 0:
            q.append(i)

    # q가 빌 때까지 진행
    while q:
        now = q.popleft()
        result.append(now)

        # now와 연결된 노드들의 진입차수-1
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    for city in result:
        if city <= W:
            total_cost += cost[city]

    print(total_cost)

T = int(input())

for _ in range(T):
    # 건물(N), 건설 순서(K)
    N, K = map(int, input().split())
    # 모든 건물에 대한 진입차수는 0으로 초기화
    indegree = [0] * (N + 1)

    # 각 건물의 건설 시간을 담을 리스트
    cost = list(map(int, input().split()))

    # 도시 번호와 인덱스 대응
    cost.insert(0, 0)

    # 각 건물의 간선 정보를 담기 위한 그래프 초기화
    graph = [[] for i in range(K + 1)]

    # 건설 순서 정보 입력
    for _ in range(K):
        X, Y = map(int, input().split())
        graph[X].append(Y)  # X -> Y
        # 진입차수 1 증가
        indegree[Y] += 1

    W = int(input())

    topology_sort()

 

성공

from collections import deque
import sys

input = sys.stdin.readline

# 위상 정렬 함수
def topology_sort():

    q = deque()
    dp = [0 for _ in range(N + 1)]

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입(1부터 v까지 체크)
    for i in range(1, K+1):
        if indegree[i] == 0:
            q.append(i)
            dp[i] = cost[i]

    # q가 빌 때까지 진행
    while q:
        now = q.popleft()

        # now와 연결된 노드들의 진입차수-1
        for i in graph[now]:
            indegree[i] -= 1

            dp[i] = max(dp[i], dp[now]+cost[i])
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    print(dp[W])

T = int(input())

for _ in range(T):
    # 건물(N), 건설 순서(K)
    N, K = map(int, input().split())
    # 모든 건물에 대한 진입차수는 0으로 초기화
    indegree = [0] * (N + 1)

    # 각 건물의 건설 시간을 담을 리스트
    cost = list(map(int, input().split()))

    cost.insert(0,0)

    # 각 건물의 간선 정보를 담기 위한 그래프 초기화
    graph = [[] for i in range(K + 1)]

    # 건설 순서 정보 입력
    for _ in range(K):
        X, Y = map(int, input().split())
        graph[X].append(Y)  # X -> Y
        # 진입차수 1 증가
        indegree[Y] += 1

    W = int(input())

    topology_sort()

 

문제 회고

 

초반에 작성한 내 코드의 경우 결국엔 내가 원하는 건물의 선행 건물들을 다 더하는 결과를 출력하는 것을 알 수 있다.