[C/C++] 백준 - 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번에서 출발해 1번으로 되돌아올 때 가장 큰 점수값과 그 경로(단, 중간에 1번을 거쳐가는 경로는 포함하지 않음)를 구하는 문제

 

일단 최장 경로 다익스트라, 위상 정렬 둘 중 하나 사용하면 풀 수 있다고 생각이 되었다. 가장 비용이 큰 경로를 구하는 문제이기 때문에 다익스트라를 생각할 수 있고, 가는 경로가 입력으로 정해져 있기 때문에 위상 정렬도 생각할 수 있었다. 나는 위상정렬로 해결하고자 하였는데 4번인가 틀려서 결국 온라인 스터디 방장(?)님께 물어봐서 해결했다.

 

내가 틀렸던 이유는 크게 2가지 이다.

1. 문제에서 주어진 조건을 제대로 보지도 않고 비용 최신화를 했다. 나는 진입차수가 0이 될 경우에만 비용 최신화 과정을 했는데, 이게 아니라 갈 수 있는 곳의 비용을 하나 하나 다 따져주어야 하기 때문에 진입차수가 0이 아니더라도 갈 수 있는 곳이라면 비용 최신화 과정을 거쳐주어야 한다. 이 부분을 간과했다.

 

2. 문제에서 주어진 조건 1번에서 출발하고 1번으로 되돌아오는 경로 중간에 1번을 거쳐지나가서는 안된다. 이 부분을 놓쳤다. 그리고 틀리고나서 찾았는데 어디 조건에 추가해야 올바르게 작동할지 헷갈렸다. 다음 갈 수 있는 노드가 1일 때는 그 노드를 큐에 넣지 않고 넘어가면 된다. 근데 이 생각을 못했다. 빠가라 그런듯

 

틀린 이유 두 가지 모두 문제에서 하라는 대로 하지 않아 틀렸다.

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 987654321
using namespace std;
typedef long long ll;
typedef struct GraphNode {
	int dest;
	int cost;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	int count;
	GraphNode* adj;
}Graph;

int inDegree[1002];
int Length[1002];
int route[1002];
queue<int> q;

void Init_Graph(Graph* gph, int count) {
	gph->count = count;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (count + 1));
	for (int i = 1; i <= count; i++)
		gph->adj[i].next = NULL;
}

int AddDirectedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

vector<int> topology_Sort(Graph* gph, int N) {
	q.push(1);
	vector<int> answer;
	while (!q.empty()) {
		int next = q.front();
		int cur = Length[next];
		q.pop();
		GraphNode* head = gph->adj[next].next;
		while (head) {	
			--inDegree[head->dest];
			if (Length[head->dest] < cur + head->cost) {
				Length[head->dest] = cur + head->cost;
				route[head->dest] = next;
			}
			if (!inDegree[head->dest] && head->dest != 1) {
				q.push(head->dest);
			}
			head = head->next;
		}
	}
	answer.push_back(1);
	int Temp = route[1];
	while (Temp != 1) {
		answer.push_back(Temp);
		Temp = route[Temp];
	}
	answer.push_back(1);
	reverse(answer.begin(), answer.end());
	return answer;
}

int main() {
	CUNLINK;
	Graph graph;
	vector<int> Answer;
	int Node_N, Edge_N;
	cin >> Node_N >> Edge_N;
	Init_Graph(&graph, Node_N);
	while (Edge_N--) {
		int From, To, Cost;
		cin >> From >> To >> Cost;
		AddDirectedEdge(&graph, From, To, Cost);
		inDegree[To]++;
	}
	Answer = topology_Sort(&graph, Node_N);
	cout << Length[1] << endl;	
	for (auto a : Answer) cout << a << " ";

	return 0;
}