2611 자동차 경주 (백준, python3)

 

시간 제한	메모리 제한
1초	128MB

문제

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

---

풀이

우선 알아야 할 개념: 위상정렬(topological sort)

위상정렬 - 위키백과, 우리 모두의 백과사전

 

우선 가능한 모든 경로를 찾아야 한다. 직접 너비우선탐색이나 깊이우선탐색을 하는 것도 방법이겠으나 "가장 점수가 큰 경로"를 찾아야 한다는 게 문제다. 그래프 탐색은 기본적으로 가중치가 작은 최단거리 우선 탐색을 한다. 그런데 이 문제의 경우 여러 경로를 찾아 가장 가중치가 큰 경로를 찾아야 한다. 가중치를 음수로 바꿔준다 해도 중복탐색을 해야하는 이상 음의 순환고리에 무조건 빠질 수밖에 없다. 모든 지점을 단 한 번씩만 지나도록 하되, 가장 큰 가중치 합을 알아볼 수 있는 방법은 없을까?

 

비순환 방향 그래프에서는 정점간의 연결 순서를 기준으로 정렬하는 위상정렬이 가능하다. 위상정렬을 하고 탐색을 시작하면 각 지점을 중복하는 것도 가능하고 모든 경로를 한 번씩만 지나가볼 수 있다. 각 지점을 지날 때마다 가중치 합을 구해주면서 가장 큰 값만 남겨주면 이 문제를 해결할 수 있다.

 

우선 1에서 출발해 1로 돌아온다. 이렇게 되면 주어진 그래프는 순환 그래프가 되는데 순환 그래프는 위상정렬을 할 수 없다. 따라서 정점을 분리해 출발점인 1과 도착점인 1을 따로 관리해주면 된다. 어차피 지점 번호가 1번부터 들어오니 도착점을 0번으로 처리해주자. 이 문제에서는 1번 지점이 반드시 시작 지점이고 처리 과정에서 진입 차수가 무조건 0으로 되기 때문에 0부터 탐색을 실시한다. 그리고 그 이후로는 탐색한 지점들의 진입차수를 1씩 깎으면서 다음 지점을 찾으면 된다. i 지점을 탐색하는 중에 연결된 지점 j의 진입차수가 0으로 바뀌었다면 다음 탐색 큐에 j를 넣어주고, 진입차수가 0이 아니라면 아직 다른 지점이 남았으므로 큐에 넣지 않는다.

 

나머지는 1번 정점부터 탐색을 시작해 각 지점까지 도착했을 때의 최대 점수를 dp로 관리해주면 된다. 0번 정점에 도달했을 때의 최대 점수가 이 문제에서 원하는 해를 구할 수 있다. 경로는 dp를 관리할 때, 갱신 될 때마다 각 지점의 이전 지점을 기록해주면 된다. 탐색이 끝났을 때 역추적으로 경로를 얻을 수 있다.

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
def solution():
    N = int(input())
    road = [dict() for _ in range(N + 1)]
    dp = [0] * (N + 1)
    tp_sort = deque([1])
    income = [0] * (N + 1)
    to = [-1] * (N + 1)
    for _ in range(int(input())):
        p, q, r = map(int, input().split())
        if q == 1: q = 0
        road[p][q] = max(road[p].get(q, 0), r)
        income[q] += 1
    while tp_sort:
        now = tp_sort.popleft()
        for next in road[now]:
            income[next] -= 1
            if income[next] == 0:
                tp_sort.append(next)
            k = dp[now] + road[now][next]
            if dp[next] < k:
                dp[next] = k
                to[next] = now
    route = []
    k = 0
    while k >= 0:
        route.append(k)
        k = to[k]
    route[0] = 1
    route.reverse()
    print(dp[0])
    print(*route)
solution()