[BOJ/Python] 2611_자동차 경주

문제 출처:https://www.acmicpc.net/problem/2611

2611번: 자동차경주

문제

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

예제 입력 1

8
13
1 2 5
1 3 4
2 5 2
2 6 1
3 6 3
5 6 7
5 8 9
6 8 3
4 1 6
6 4 8
7 4 5
6 7 2
8 7 4

예제 출력 1

32
1 2 5 6 8 7 4 1

---

풀이

 

문제를 요약하면 다음과 같다.

 

1. 자동차는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아온다.
2. 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아와야 한다.
3. 이때 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾고, 그 점수와 경로를 출력하는 문제이다.

위상정렬과 DP를 이용하여 문제를 해결할 수 있다.

코드는 다음과 같다.

 

import sys
import collections
 
def topological_sort():
    queue =collections.deque()
    queue.append((0,1))
 
    while queue:
        dist,node = queue.popleft()
 
        for next,r in graph[node]:
            if score[next]< r+dist:
                score[next] = r+dist
                parent[next] = node
            
            indegree[next]-=1
            if indegree[next] ==0:
                if next==1:
                    return
                queue.append((score[next],next))
 
 
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
 
graph = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
parent = [i for i in range(n+1)]
score = [0 for _ in range(n+1)]
for _ in range(m):
    p,q,r = map(int,sys.stdin.readline().split())
    graph[p].append((q,r))
    indegree[q]+=1
 
topological_sort()
 
result = [1]
p = parent[1]
while p!=1:
    result.append(p)
    p = parent[p]
result.append(1)
 
print(score[1])
print(*result[::-1])

1. 우선 도로(간선들의 정보)를 입력받는다. 또한 각 지점으로 들어오는 도로가 있다면 진입차수를 1 증가시킨다.
2. 위상정렬을 수행한다.
3. 여기서 score 리스트는 그 지점까지 얻을 수 있는 최대의 점수를 의미한다.
4. 문제에서 주어진 <그림2>에서 6번 지점의 경우, 3번 지점을 거칠 경우 7점이지만 2번 지점과 5번 지점을 거칠 경우 14점을 획득할 수 있으므로 1번 지점 -> 2번 지점 -> 5번 지점 -> 6번 지점의 경로가 훨씬 유리하다.
5. 만약 이처럼 보다 유리한 경로(많은 점수를 획득할 수 있는 경로)를 발견한다면, 해당 지점의 score 값을 경신하고, 어떤 지점을 통하여 현재 지점으로 도달하였는지 parent [현재 지점] = 이전 지점으로 갱신한다.
6. 최종적으로 위상정렬을 수행하고 나면 score[1]에는 1번 지점으로 도달하였을 때 얻을 수 있는 최대 점수가 저장되게 된다.
7. 이후 1번의 이전 지점부터 하나씩 result 리스트에 저장하고, 최종적으로 저장된 순서를 뒤집으면 어떠한 경로로 1번 지점에 도달하였는지 알 수 있다.