[BOJ_Gold 2] - 2611 자동차 경주 [python]

문제

자동차 경주로는 <그림 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번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다.

 

---

위상정렬을 이용한 문제입니다.

주어진 그래프는 다음의 그림과 같은 DAG로 나타낼 수 있고, 이를 통해 위상정렬을 진행할 수 있습니다.

 

 

 위상정렬 이후, 역방향 그래프를 통해 DP값을 역추적하며 최적의 경로를 구하면 됩니다.

 

import sys
from typing import List
from collections import deque
input = sys.stdin.readline

ansRoute = [1]

def backTracking(node : int) -> List: # 거슬러 올라가기
    #하나만 취하면 되므로 그냥 쭉쭉 따라가면 됨
    global ansRoute

    for nextnode,cost in rv_graph[node]:

        if nextnode == 1 and dp[node] - cost == 0:
            print(*(ansRoute + [1])[::-1])
            exit()

        if dp[nextnode] == dp[node] - cost:
            ansRoute.append(nextnode)
            backTracking(nextnode)


n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
rv_graph = [[] for _ in range(n + 1)]

dp = [-float("inf")] * (n + 1)
indegree = [0] * (n + 1)
for i in range(m):
    f,t,cost = map(int,input().split())
    graph[f].append((t, cost))
    rv_graph[t].append((f, cost))
    indegree[t] += 1

queue = deque([1])  #1번 노드에서 무조건 시작

#모든 노드는 1번 의존성을 가짐 --> 적어도 하나의 노드는 부모로 1만을 가져야 한다 --> 위상정렬 가능
dp[1] = 0
while indegree[1]: # --> 1번이 끝났다는건 탐색 전체가 종료됐다는 것
    # (모든 노드는 1번으로 가는 경로가 존재하기 때문
    node = queue.popleft()

    for nextnode,cost in graph[node]:
        indegree[nextnode] -= 1
        dp[nextnode] = max(dp[nextnode], dp[node] + cost)

        if not indegree[nextnode]:
            queue.append(nextnode)

print(dp[1])
backTracking(1)

 

 

아래는 Top-Down 풀이입니다.

 

Top-Down방식의 경우,

역추적 또한 루트노드부터 진행하기때문에 별도의 역방향 간선이 필요하지 않습니다.

 

import sys
from typing import List
sys.setrecursionlimit(1000)

input = sys.stdin.readline

ansRoute = [1]

def backTracking(node : int) -> List: # 거슬러 올라가기
    #하나만 취하면 되므로 그냥 쭉쭉 따라가면 됨
    global ansRoute
    for nextnode,cost in graph[node]:

        if nextnode == 1 and dp[node] - cost == 0:
            print(*(ansRoute + [1]))
            exit()

        if dp[nextnode] == dp[node] - cost:
            ansRoute.append(nextnode)
            backTracking(nextnode)

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]

dp = [-1] * (n + 1)

for i in range(m):
    f,t,cost = map(int,input().split())
    graph[f].append((t, cost))

#모든 노드는 1번 의존성을 가짐 --> 적어도 하나의 노드는 부모로 1만을 가져야 한다 --> 위상정렬 가능
def dfs(node : int) -> int:
    if dp[node] != -1: return dp[node]

    for nextnode,cost in graph[node]:
        dp[node] = max(dp[node],(dfs(nextnode) + cost if nextnode != 1 else cost))
    return dp[node]

print(dfs(1))
backTracking(1)