문제

건물의 건설 순서와 시간이 주어졌을 때, 특정 건물을 짓기 위해 걸리는 시간 구하기

풀이

본 문제는 위상 정렬 (Topology Sort)과 동적 계획법 (Dynamic Programming) 문제이다. 위상 정렬이란, 유향 그래프 (Directional Graph)의 꼭짓점을 변의 방향을 거스르지 않고 나열하는 것을 의미한다.

일반적인 위상정렬 알고리즘은 다음과 같이 실행된다.

1. 부모 노드가 존재하지 않는 노드를 queue에 넣는다.
2. queue에서 원소를 하나씩 빼면서, 해당 노드로부터 갈 수 있는 모든 노드들에 대한 연결을 제거한다.
3. 앞선 과정을 반복한다.

그러나 본 문제는 건설 순서를 묻는 것이 아니라, 특정 건물을 짓기 위해 필요한 최소 시간을 구하는 것이기 때문에, 여기서 추가적인 접근을 해줘야 한다.

따라서 $n$번째 건물을 짓기 위해서는, $n-1$번째 건물을 짓기 위한 시간의 최대값을 구하는 다이나믹 프로그래밍을 통해 문제를 풀고자 하였다.

코드

입력값 받기

    num_buildings, num_order = map(int, input().split()) # 빌딩 개수, 순서 개수
    t_build = [0] + list(map(int, input().split())) # 빌딩 시간
    matrix = [[] for _ in range(num_buildings+1)]
    num_parents = [0] * (num_buildings+1)

    for _ in range(num_order):
        a, b = map(int, input().split())
        matrix[a].append(b)
        num_parents[b] += 1

    obj = int(input())

• num_buildings : 지을 수 있는 건물의 개수
• num_order : 건물과 건물 간의 건설순서 규칙의 개수
• t_build : 건물을 짓기 위해 걸리는 시간
• matrix : 건물과 건물 간의 건설 순서
  • matrix[i] : i번째 건물을 지은 이후 지을 수 있는 건물들
• num_parents: i번째 건물의 부모 노드의 개수

풀이 1 (틀림)

    # 위상 정렬

    q = deque([]) # index, level

    for i in range(1,len(num_parents)):
        if num_parents[i] == 0:
            q.append((i,0))
            num_parents[i] = -1

    init_level = 0
    time_consumed = [0] * (len(num_parents)+1)

    while q:

        index, level = q.popleft() # 원소를 가져온다.

        # 가져온 원소가 obj일 경우 loop 탈출
        if index == obj:
            result = time_consumed[level-1] + t_build[index]
            break

        # 해당 level에서 어느 건물을 짓는 것이 더 오래 걸리는지 확인
        time_consumed[level] = max(time_consumed[level], time_consumed[level-1] + t_build[index])

        # 다음 건물 리스트 추가

        ## 자녀노드 향한 간선 끊기
        children = matrix[index]

        for child in children:
            num_parents[child] -= 1

        ## 부모 없는 노드들 queue에 넣기
        for i in range(1, len(num_parents)):
            if num_parents[i] == 0 :
                q.append((i, level+1))
                num_parents[i] = -1

    print(result)

우선 부모 노드의 개수가 0개인 노드들을 q에 넣는다. 이 때, level과 함께 튜플의 형태로 넣는데, level은 해당 건물을 짓기 위해 이전에 지어야 하는 건물의 개수를 의미한다.

이후, 해당 level에서 건물을 지을 때의 최대값을 계산한 후 앞서 말한 위상정렬의 순서를 반복한다.

그러나 해당 코드는 58%에서 "틀렸습니다"가 출력되었는데, 이는 네트워크가 여러 개일 경우를 고려하지 못했기 때문이다.

만약 건물이 10개가 있다고 생각해보자. $n$번 건물을 짓는 데에는 $n$만큼의 시간이 소요된다. 그리고 $n+5$번 건물을 짓기 위해서는 $n$번 건물을 먼저 지어야 한다고 생각해보자.

즉, 6번 건물을 짓기 위해선 1번 건물을, 7번 건물을 짓기 위해서는 2번 건물을 먼저 지어야 한다.

나는 6번 건물을 짓고 싶다고 가정하자.

위상 정렬 알고리즘에 따라 1번 건물부터 5번 건물은 부모 노드가 없기 때문에 우선적으로 queue에 삽입된다. 5개의 건물은 선행 건물이 없으므로 level 0이고, 위 알고리즘은 level에 따라 건물을 짓는 시간을 계산하므로 time_consumed[0]은 이 중 최대값은 5가 된다.

그러나 6번 건물을 짓기 위해서는 1번 건물만 지으면 된다. 따라서 실제 소요시간은 1+6=7초지만, level = 0의 건설 시간이 5기에 5+6=11초로 계산이 된다.

따라서 다양한 네트워크가 존재할 경우의 수를 고려하여, level별로 건축 시간을 계산하기 보다는 건물 별로 건축 시간을 계산하기로 하였다.

풀이 2

    # 위상 정렬

    ## 제일 처음 root들에 대한 처리
    q = deque([]) # index, level

    for i in range(1,len(num_parents)):
        if num_parents[i] == 0:
            q.append(i)
            num_parents[i] = -1

    init_level = 0
    time_consumed = [0] * (len(num_parents)+1)

    for q_value in q:
        time_consumed[q_value] = t_build[q_value]

    
    while q:

        #print(f"before q {q}")
        #print(f"before t {time_consumed}")

        building = q.popleft() # 빌딩 가져오기

        if building == obj:
            break

        # 다음 빌딩들에 대해서 최대값 갱신
        next_buildings = matrix[building]

        for next_building in next_buildings:
            time_consumed[next_building] = max(time_consumed[next_building], time_consumed[building] + t_build[next_building])
            ## 부모와의 간선 끊기
            num_parents[next_building] -= 1

        # 부모 없는 빌딩 가져오기
        for i in range(1, len(num_parents)):
            if num_parents[i] == 0:
                q.append(i)
                num_parents[i] = -1

        #print(f"after q {q}")
        #print(f"after t {time_consumed}")

    #print(f"result : {time_consumed[obj]}")
    print(time_consumed[obj])