(BOJ1005 ACM Craft

• tags : (algorithm

  No matching post could be found

  - (topological sort
• 문제 링크 : https://www.acmicpc.net/problem/1005
• 풀이 링크
  • Python

• 위상 정렬을 활용하여 특정 순서의 건물이 지어지는 시간을 구하는 문제
• 이 문제에서는 각 건물을 짓는데 걸리는 시간을 누적해 가야한다.
  • 그리고 이 시간을 위상 정렬에 맞게 처리해야 하므로 정렬 순서와 각 건물을 짓는데 걸리는 시간 등을 잘 확인하고 관리해야 한다.

N, K = MIIS()
buildings = [0] + list(MIIS())
before_count = [0] * (N + 1)
next_building = [[] for _ in range(N + 1)]
for _ in range(K):
    x, y = MIIS()
    next_building[x].append(y)
    before_count[y] += 1

• 우선 주어진 건물순서를 받아서 before_count에는 각 건물보다 먼저 지어져야 하는 건물의 수를, next_building에는 특정 건물 다음에 지을 수 있는 건물 번호를 저장한다.

build_times = [0] * (N + 1)
queue = deque([])
W = II()
for i in range(1, N + 1):
    if not before_count[i]:
        if i == W:
            print(buildings[i])
            break
        build_times[i] = buildings[i]
        queue.append((i, buildings[i]))
else:
    while queue:
        x, t = queue.popleft()
        for y in next_building[x]:
            if build_times[y] < t + buildings[y]:
                build_times[y] = t + buildings[y]
            before_count[y] -= 1
            if not before_count[y]:
                queue.append((y, build_times[y]))
                if y == W:
                    print(build_times[W])
                    break
        else:
            continue
        break

• W건물을 짓는데 걸리는 시간을 구하기 위해 BFS를 응용한다.
• 우선, 위에서 구한 값을 기반으로 선행 건물이 없는 건물을 queue에 넣는다.
  • 만약 W 건물이 가장 먼저 지어질 수 있다면 해당 건물을 짓는데 걸리는 시간을 출력하고 종료한다.
• 다음 queue에 들어있는 건물을 확인하여 위상정렬을 수행한다.
  • 각 건물을 확인하며, 다음 순서에 지을 수 있는 건물도 확인한다.
  • 모든 건물을 확인할 때마다 시간을 갱신한다. 이 때 시간은 최대한 늦는 시간으로 갱신한다.
  • 그리고 건물이 지어질 수 있다면 queue에 추가하여 탐색한다.