[백준 1948번] 임계경로 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)

def countpath(now):
  global cnt
  if visited[now]:
    return
  visited[now] = 1
  for last in path[now]:
    cnt += 1
    countpath(last)

N,M = int(input()),int(input())

graph = [[] for i in range(N+1)]
indegree = [0]*(N+1)
for _ in range(M):
  x,y,w = map(int,input().split())
  graph[x].append((y,w))
  indegree[y] += 1
start,end = map(int,input().split())

DP = [0]*(N+1)
path = [[] for i in range(N+1)]
dq = deque()
dq.append(start)
while dq:
  now = dq.popleft()
  for next,w in graph[now]:
    indegree[next] -= 1
    if DP[next] == DP[now]+w:
      path[next].append(now)
    elif DP[next] < DP[now]+w:
      DP[next] = DP[now]+w
      path[next] = [now]
    if not indegree[next]:
      dq.append(next)

cnt,visited = 0,[0]*(N+1)
countpath(end)
print(DP[end])
print(cnt)

문제를 잘못 해석해서 며칠을 고생한 문제이다.

당연히 지도를 그린다고 해서 모든 "도로"를 탐색할 때 최대시간을 구하는 문제인 줄 알았다.

그런데 그게 아니라 모든 "경로"를 탐색하는 문제였다. 대체 왜 지도를 만드는데 모든 "도로" 가 아니고 모든 "경로" 를 탐색하는건지 이해가 안가지만 풀이는 훨씬 간단하다.

 

기본적으로 모든 도로가 사이클이 없는 일방통행이기 때문에 위상정렬을 이용할 수 있다. 최장경로를 구하는 문제이므로, ACM Craft [백준 1005번] ACM Craft (Python3) (tistory.com) 문제와 거의 비슷하다. ACM Craft에서 경로 역추적만 추가한 느낌.

 

즉, 위상정렬로 최장저리를 찾고, 이때의 경로를 저장하고, 경로를 역추적하면 되는 문제이다.

 

 

오늘의 교훈) 문제를 꼼꼼이 읽고 넘겨짚지 말자