백준 1432_그래프 수정

임계경로(백준 1948)

https://www.acmicpc.net/problem/1948

위상정렬을 사용하여 최대 경로값을 구하고,
set을 사용하여 경로의 중복을 제거한다는 접근 방식은 좋았으나
set() 하나만 가지고 어떤 방식으로 접근을 할지까지는 생각이 닿지 못했다

이후 검색을 통해 ‘역추적’이라는 방식을 알아내었고,
그에 따라 그래프를 뒤집은 후
미리 따라가며, 저장해둔 도시 인덱스를 집어넣어가며
중복을 제거하는 방식을 이용하였다

[참고] : https://velog.io/@hanbin/%EB%B0%B1%EC%A4%80-1948%EB%B2%88-%EC%9E%84%EA%B3%84%EA%B2%BD%EB%A1%9C-with-Python

Code

import sys
from collections import deque
inp = sys.stdin.readline

n = int(inp().strip())
m = int(inp().strip())

cities = [[] for _ in range(n)]
reverCity = [[] for _ in range(n)]
inDegree = [0 for _ in range(n)]

for i in range(m):
    st, t, cost = map(int,inp().split())
    cities[st-1].append([t-1,cost])
    reverCity[t-1].append([st-1,cost])
    inDegree[t-1] += 1

start,to = map(int,inp().split())
 
que = deque()

for i in range(n):
    if inDegree[i] == 0:
        que.append(i)
        
answer = [[0,[]] for _ in range(n)]

while que:
    cityIndex = que.popleft()

    for targetCity, targetCost in cities[cityIndex]:
        if answer[targetCity][0] < answer[cityIndex][0] + targetCost:
            answer[targetCity][0] = answer[cityIndex][0] + targetCost
            answer[targetCity][1] = [cityIndex]
        elif answer[targetCity][0] == answer[cityIndex][0] + targetCost:
            answer[targetCity][1].append(cityIndex)
 
        inDegree[targetCity] -= 1
        if inDegree[targetCity] == 0:
            que.append(targetCity)

bQ = deque([to-1])
route = set()

while bQ:
    curr = bQ.popleft()
    for i in answer[curr][1]:
        if (curr,i) not in route:
            route.add((curr,i))
            bQ.append(i)

print(answer[to-1][0])
print(len(route))

해결 아이디어

1. 방향성, 비 사이클이 보장되어 있는 문제이기에
   ‘위상정렬’ 을 사용할 수 있다 판단하였고,
   inDegree 배열을 사용하여 체크하였다
2. 이후 while 반복을 통해, ‘목적지’에 도달할 때까지의
   가장 높은 비용의 합을 계산하며
   동시에, 해당 경로 시점에서 ‘시작 도시’에 대한 데이터를 저장
   
3. 이후 백트래킹을 위한 que와 set을 만들고,
   목표 지점에서 다시 시작점으로 ‘저장한 도시’를 향해 돌면서
   경로를 set에 넣어준다
4. 목적도시의 최대 도착값과
   set 경로의 길이를 반환