[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리7(임계경로)

BOJ 1948 임계경로

난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 플5

사용 알고리즘 or 자료 구조 : 위상정렬, 그래프 이론

처음 생각한 풀이

이전 문제인 그래프 수정을 접근법을 안보고 풀기도 했고, 백준 기준 난이도가 더 어려워서 솔직히 물로 봤다.

 

그도 그럴게 그래프 수정은 플4고 이거는 플5이기도 하고 문제를 이해하는게 더 쉬웠고 접근 방법도 더 쉬워보였기 때문이다.

 

하지만 그렇지 않았다.

 

처음에는 단순히 각 노드 별로 걸린 시간과 경로를 저장해놓는 배열을 선언하여 위상정렬을 하는 과정에서 해당 데이터를 이용하여 다음 노드에 데이터를 저장하는 식으로 풀었다.

 

하지만 지금 생각해보면 도시의 개수는 최대 10,000개, 도로의 개수는 최대 100,000개 였기 때문에 메모리가 터지지 않을 수가 없었다.

 

문제 예제와 질문 게시판에 있는 일부 반례들은 맞게 나오는걸로 보아 아이디어 자체는 맞게 짠 것 같았지만, 메모리나 시간이 초과되는 코드가 뭔 소용이 있나 하고 고민을 하다가 접근법을 질문 게시판을 통해 찾아봤다.

접근법 이후 풀이

접근법은 각 노드 별로 그 노드까지 오는데 걸리는 최대 시간을 저장하는 배열을 선언하여 최대 시간을 구하는 것부터 시작한다.

 

물론 이 과정에서 위상 정렬이 필요하긴 하다. 안하면 메모리가 터지거나 시간이 터질 수 있으므로 반드시 위상 정렬 요소를 첨가하여 queue의 크기를 잘 관리하도록 하자.

 

최대 시간을 구했으면 이번에는 도착 노드에서 역으로 올라가면서 경로의 개수를 세야한다.

 

처음엔 문제도 잘못 이해해서 예제 문제의 답에서 경로의 개수가 왜 5개지 하고 생각을 해봤는데, 경로의 개수가 아니라 최대 시간이 걸린 사람이 지나온 도로의 개수를 세는 것이라고 생각하면 이해가 편하다.

 

도착 노드에서 거슬러 올라가는 과정은 처음 입력을 받을 때 a b c 로 데이터가 주어졌으면 a -> b로 가는 길이 c 인 것만 저장하는 것이 아니라 거슬러 올라가는데 시간이 얼마나 드는지를 저장해야한다.(b -> a 로 가려면 c가 걸린다 를 저장해야함)

 

그렇게 한 다음 '도착 노드의 최대 시간' - '해당 도로를 지나가는데 걸리는 시간' == '이전 노드에서의 최대 시간' 이라면 해당 도로는 최대 시간이 걸린 사람이 지나온 길이 맞으므로 정답 + 1 을 시켜주면 된다.

 

여기서 조심해야되는 것은 중복된 길을 다시 지나올 수 있다는 것이다.

나는 outdegree 값을 이용하여 중복 문제를 해결하려 했지만 해결이 불가능해 결국 여기서 답을 참고했다.

 

답은 visited 배열을 선언해서 한번 방문한 노드에 대한 도로는 다시 지나가지 않도록 하여 중복을 해결하는 것이다.

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

코드

import sys

from collections import deque

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

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

indegree = [0 for _ in range(n + 1)]

edge = [[] for _ in range(n + 1)]

revedge = [[] for _ in range(n + 1)]

for i in range(m):

    a, b, c = map(int, sys.stdin.readline().split())

    edge[a].append([b, c])

    revedge[b].append([a, c])

    indegree[b] += 1

start, end = map(int, sys.stdin.readline().split())

anstime = 0

ansroute = 0

queue = deque(maxlen = 10000)     ### 현재 노드 정보

maxT = [0 for _ in range(n + 1)]    ### index번 노드까지 오는데 걸린 최대 시간

queue.append(start)

while queue:

    cur = queue.popleft()

    for next in edge[cur]:

        nnode = next[0]

        ntime = next[1]

        indegree[nnode] -= 1

        maxT[nnode] = max(maxT[cur] + ntime, maxT[nnode])

        if indegree[nnode] == 0:

            queue.append(nnode)

anstime = maxT[end]

queue.clear()

queue.append(end)

visited = [False for _ in range(n + 1)]

while queue:

    cur = queue.popleft()

    for prev in revedge[cur]:

        pnode = prev[0]

        ptime = prev[1]

        if maxT[cur] - ptime == maxT[pnode]:

            ansroute += 1

            if visited[pnode]:

                continue

            queue.append(pnode)

            visited[pnode] = True

print(anstime)

print(ansroute)