[BaekJoon] 1005: ACM Craft

BaekJoon 1005: ACM Craft

풀이 방법

위상 정렬 topological sorting 과 DP를 활용하여 문제를 해결한다. 인접 리스트를 사용해 유향 그래프를 만들고, 진입 간선의 수를 체크하기 위해 degree 배열을 만들어 준다. 정점을 모두 담을 큐도 하나 선언해 준다.

from collections import deque
time = [0] + list(map(int, input().split())) # time to build
result = time.copy()

degree = [0] * (N + 1)
graph = [[] for _ in range(N+1)]
queue = deque([i+1 for i in range(N)])

먼저, 건물을 짓는 순서 X, Y 가 주어질 때마다 인접 리스트로 구현된 그래프와 차수 배열을 업데이트하여 그래프를 완성해 준다. 그 후 위상 정렬을 사용하여 건물을 짓는 순서대로 정렬하고, 순서가 결정될 때 마다 해당 정점과 인접한 정점의 건물을 지을 때 걸리는 시간을 업데이트한다. 예를 들어 문제에서 주어진 것과 같은 다음 그래프가 있다고 하자.

그래프 자료구조
vertex: 0 - none
vertex: 1 - 2, 3
vertex: 2 - 4
vertex: 3 - 4

위상 정렬 수행과정

큐에서 정점 1를 pop
정점 1의 진입 간선은 없습니다.
정점 1와 인접한 정점 2의 result 를 업데이트하고 간선 <1, 2>를 삭제합니다.
정점 1와 인접한 정점 3의 result 를 업데이트하고 간선 <1, 3>를 삭제합니다.
큐에서 정점 2를 pop
정점 2의 진입 간선은 없습니다.
정점 2와 인접한 정점 4의 result 를 업데이트하고 간선 <2, 4>를 삭제합니다.
큐에서 정점 3를 pop
정점 3의 진입 간선은 없습니다.
정점 3와 인접한 정점 4의 result 를 업데이트하고 간선 <3, 4>를 삭제합니다.
큐에서 정점 4를 pop
정점 4의 진입 간선은 없습니다.
위상 정렬 종료

시행착오

• DFS, DP 등등 여러 방법을 고민해 보다가 도저히 안 되겠어서 검색을 통해 '위상 정렬'을 알게되었다. 골드 단계부터 여러 알고리즘들을 복수로 적용하여 풀이하는 문제가 많아진다고 하니 참고할 것..
• 처음에는 double linked list 처럼 각 정점의 in&out 간선을 모두 저장했으나, 위상 정렬에는 진입 간선의 수만 체크하면 되므로 degree 배열을 사용하여 해결하였다. 단순히 답만 나온다고 끝이 아니라, 최적화할 수 있는 방법을 고민해 보자.
• 로컬에서는 돌아가는 코드가 백준 Python3 으로 제출했을 때 시간 초과될 경우, PyPy3 으로 제출해 볼 것.

전체 코드

from collections import deque

T = int(input())

for i in range(T):
    N, K = map(int, input().split())

    time = [0] + list(map(int, input().split()))
    result = time.copy()

    degree = [0] * (N + 1)
    graph = [[] for _ in range(N+1)]
    queue = deque([i+1 for i in range(N)])

    # graph as adjacency list
    for _ in range(K):
        src, des = map(int, input().split())
        graph[src].append(des)
        degree[des] += 1

    # topological sort
    while(queue):
        v = queue.popleft()
        if not degree[v]:
            for i in graph[v]:
                result[i] = max(result[i], result[v] + time[i])
                degree[i] -= 1
        else:
            queue.append(v)

    W = int(input())
    print(result[W])