[백준] 1005 ACM Craft

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

문제를 접하고 도착하는 노드에서 거꾸로 BFS 탐색을 이용해 같은 거리만큼 떨어진 노드들의 시간들 중 가장 오래 걸리는 시간을 기록하여 구하려 하였습니다.

그러나 시간초과 문제가 발생하였고, 원인을 정확히 파악하지 못하였으나 거꾸로 진행하는 방식은 값을 구하는 과정에서 오류가 발생할거 같다는 생각이 들었습니다.

(건물이 순서대로 건설 되는것이 아니라 병렬적으로 건설이 가능하여 노드들의 위치와 필요한 건물들의 상황에 따라 최소 시간에 오류가 발생)

 

그래서 앞에서부터 진행하는 방식을 이용하였습니다.

다음 노드에서 단방향으로 들어오는 간선의 개수를 카운트하고 그 카운트가 0이 되었을때 다음 노드를 실행하도록 하였습니다.

2) 알고리즘

• 다이나믹 프로그래밍
• 위상 정렬

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

T = int(sys.stdin.readline())

for _ in range(T):
    N, K = map(int, sys.stdin.readline().split())                   # 건물의 개수, 건설 순서 규칙의 개수
    delays = [0] + list(map(int, sys.stdin.readline().split()))     # 건물을 짓기 위한 소요 시간
    linked = [[] for _ in range(N+1)]                               # 건설 순서
    needs = [0] * (N+1)                                             # 현재 건물을 짓기 위해 필요한 건물 개수
    dp = [0] * (N+1)                                                # 현재 건물을 짓는데 소요되는 최소 시간

    for _ in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        linked[X].append(Y)                                         # 현재 건물이 완성되면 건설할 수 있는 다음 건물 추가
        needs[Y] += 1                                               # 다음 건물이 짓기 위해 필요한 건물 개수 추가

    W = int(sys.stdin.readline())                                   # 목표 건물
    q = deque()                                                 
    for i in range(1, N+1):                                         # 건설하기 위해 필요한 건물 개수가 0개인 노드 탐색
        if not needs[i]:
            q.append(i)                                             # 탐색을 위한 큐에 추가
            dp[i] = delays[i]                                       # 시작 건물들의 건설 소요 시간 입력

    while q:
        node = q.popleft()
        for next in linked[node]:
            dp[next] = max(dp[node] + delays[next], dp[next])       # 다음 건물의 소요시간은 현재 건물까지 소요시간+다음건물 소요시간
                                                                    # 지금까지 기록된 다음 건물 소요시간 중 큰 값 저장
            needs[next] -= 1                                        # 다음 건물이 필요한 건물 수 하나 제거
            if not needs[next]:                                     # 다음 건물 건설이 가능해지면 큐에 추가
                q.append(next)

    print(dp[W])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

역방향으로 탐색하였을때 시간초과 문제가 발생하였습니다.

시간 초과 이유와 오답에 대한 가능성을 확인하는 과정에 어려움을 겪었습니다.

2) 새롭게 학습한 내용

위상 정렬

---

🔗 문제 링크

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

1005번: ACM Craft

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다