[자동차경주/G2/Python3]

2611번 자동차경주 G2

 

문제
자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다. 자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다. 각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다. 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p , q , r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. N은 1000 이하의 자연수이고, p와 q는 1 이상의 N이하의 자연수이며 r은 100이하의 자연수이다. p와 q는 같지 않다.

출력
가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그 경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그중 하나만 출력하면 된다.

 

 

다이나믹  프로그래밍, 그래프 이론, 방향 비순환 그래프, 위상 정렬

 

위상 정렬 + DP 로 풀이하였다.

 

같은 점수인 경로가 둘 이상일 경우 아무거나 출력해도 된다.

가장 마지막에 점수를 갱신한 지역을 저장하는 DP를 만들어 사용했다.

 

 

 

 

import sys
from collections import deque

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

routes = [[] for _ in range(n+1)]
cnts = [0] * (n+1)
dp = [0] * (n+1)
recent_dp = [1] * (n+1)

for _ in range(m):
    s, e, c = map(int, sys.stdin.readline().split())
    cnts[e] += 1
    routes[s].append((e, c))

dq = deque([1])
cnts[1] = 0

while dq:
    s = dq.popleft()
    for e, c in routes[s]:
        cnts[e] -= 1
        if cnts[e] == 0:
            dq.append(e)
        
        if dp[e] > dp[s] + c: continue
        dp[e] = dp[s] + c
        recent_dp[e] = s

last = recent_dp[1]
stk = [1, recent_dp[1]]
while last != 1:
    stk.append(recent_dp[last])
    last = recent_dp[last]
stk.reverse()


print(dp[1])
print(*stk)​

 

---