[백준 1005] ACM Craft

1. 문제

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

2. 접근 방법

위상정렬 알고리즘을 사용하면됩니당

최근에 위상정렬을 알게되어 ^-^.. (그래프 문제 너무 어려워영ㅇ엉어엉엉)
풀어보았습니다.

여튼 위상 정렬 알고리즘은 다음과 같은 로직을 가집니다.

1. 진입차수가 0인 노드를 큐에 넣는다(시작점)
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

문제는 도착 지점까지 제일 오래 걸리는 시간을 찾으면 되므로, answer를 이용해서 각 노드까지 도착하는 최대 시간을 계속 갱신해줍니다. 그러다가 해당 노드의 진입차수가 0이 될 경우, 그 때 queue에 해당 노드를 집어 넣게 됩니다. 그렇게 하다가 queue에서 도착지점이 append되고, popleft되었을 때 (진입차수가 0일 때), 그 때의 값이 최대 값이므로 답이 됩니다 !

 

• 시간 복잡도: O(V+E)
  위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거합니다.
  따라서 노드와 간선을 모두 확인하게되어 이와 같은 시간 복잡도가 나옵니다.

3. 코드

python

from collections import deque, defaultdict


def solution():
    N, K = map(int, input().split())
    times = [0] + list(map(int, input().split()))   # 건설하는데 걸리는 시간
    indegree = [0] * (N+1)   # 진입차수
    graph = defaultdict(list)
    for _ in range(K):
        x, y = map(int, input().split())
        graph[x].append(y)
        indegree[y] += 1
    GOAL = int(input())

    start = []
    for i in range(1, N+1):
        if indegree[i] == 0:
            start.append(i)

    q = deque()
    for s in start:
        q.append(s)

    answer = times[:]

    while q:
        n = q.popleft()
        if n == GOAL:
            break
        answer.append(n)
        for i in graph[n]:
            answer[i] = max(answer[i], answer[n]+times[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    return answer[GOAL]


T = int(input())
for _ in range(T):
    print(solution())

4. 마치며

저는 defaultdict를 사용했는데용 어차피 1~N까지니까 graph = [[] for _ in range(N+1)]로 해줘도 될 것 같슴다.