[백준 2611] 자동차경주

문제 링크 : 2611번: 자동차경주 (acmicpc.net)

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

---

 

다이나믹 프로그래밍을 활용한 위상 정렬 문제이다.

 

문제 접근 방식은 다음과 같다.

0. 현재 노드(p)와 다음 노드(q), 그리고 다음 노드로 향하는 점수(r)를 갖고 위상 정렬 세팅을 진행한다.

• vector<pair<int, int>> road[1001] (ex : road[p] = {(q1, r1), (q2, r2), ... (qn, rn)})
• inDegree[1001] (ex : inDegree[5] = 3 즉, 노드 5의 진입 차수가 3을 의미)

1. 큐 Q를 설정하여 시작(1) 노드를 push 한다.

 

2. Q에서 꺼낸 노드를 cur 이라고 할 때, next 노드와 점수 r을 가지고 다이나믹 프로그래밍을 한다.

이때, dp[x] = "x 노드로 진입할 때의 최대 점수" 로 정의하고 parent[x] = "x 노드의 부모 노드" 로 정의한다.

• dp[cur] + r > dp[next] : dp[next] 값을 업데이트 함과 동시에 next 노드의 부모 노드를 cur 노드로 변경한다.
• dp[cur] + r ≤ dp[next] : 해당 경우는 continue 한다.

 

3.  inDegree[next] 를 1 감소시킨 값이 0이 될 때 큐 Q에다가 next 노드를 push 한다.

 

4. 2, 3을 반복하면서 끝(1) 노드를 발견할 때 inDegree[1] 값이 0일 경우 반복을 종료한다.

... 4번 경우를 고려하지 못하여 맞왜틀을 3번이나 하였다. (하나의 경험이라고 생각하기)

 

위와 같은 작업이 끝나면 다음과 같은 결과를 얻을 수 있다.

• dp[1] = 1번 지점에서부터 1번 지점으로의 최대 점수
• parent[1] = a, parent[a] = b, ..., parent[x] = 1 즉, 최대 점수를 형성하는 경로

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 1000000000
#define endl '\n'

using namespace std;

int N, M;
vector<pair<int, int>> road[1001];
int inDegree[1001];
int dp[1001], parent[1001];

void input() {
	int p, q, r;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> p >> q >> r;
		road[p].push_back({ q,r });
		inDegree[q]++;
	}
}

void print_road(int x, int s) {
	if (x == s) {
		cout << x << " ";
		return;
	}
	print_road(parent[x], s);
	cout << x << " ";
}

void solution(int s) {
	int cur, next, tmp;
	queue<int> Q;
	
	Q.push(s);
	dp[s] = 0;
	while (!Q.empty()) {
		cur = Q.front();
		Q.pop();
		if (cur == s && inDegree[s] == 0) break;

		for (int i = 0; i < road[cur].size(); i++) {
			next = road[cur][i].first;
			if ((tmp = dp[cur] + road[cur][i].second) > dp[next]) {
				dp[next] = tmp;
				parent[next] = cur;
			}
			if (--inDegree[next] == 0) {
				Q.push(next);
			}
		}
	}

	cout << dp[s] << endl;
	print_road(parent[s], s);
	cout << s;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution(1);

	return 0;
}