백준 2611 - 자동차경주(C++)

문제 링크입니다! https://www.acmicpc.net/problem/2611

2611번: 자동차경주

문제 조건

출력 예시

위상정렬과 DP를 활용해서 최대 점수를 구하고, 경로를 구하는 문제였습니다.

예를 들어 1 -> 2 -> 3 -> 5 or 1 -> 4 -> 7 -> 5의 경로가 있다고 가정하겠습니다.

5번을 도착하기 위해서는 3번과 7번을 거쳐가는 2가지 방법이 있습니다. 

이때 최댓값을 구하기 위해서는 3번까지 왔을 때의 값과 7번까지 왔을 때의 값을 비교하면 됩니다.

3번과 7번의 값을 구하는 방법은 2가지가 있습니다. 

1. 3 -> 2 -> 1로 가면서 해당 경로의 값을 구하는 방법

2. 각각의 점에서의 최댓값을 구하는 방법

1번 방법의 경우 경로가 많아질 경우 시간 초과가 생김으로 2번을 사용해 최댓값을 구하는 방식으로 구해야합니다.

 

경로의 경우에는 N번을 갔을 때, N번 이전까지의 경로를 저장해둔 뒤, N번에서의 최댓값이 바뀔 때마다 경로를 수정해주는 방법을 사용했습니다.

 

문제 접근 방법

1. 출발점, 도착점, 비용을 저장한다.

2. 1번 점에서 출발하여 연결된 점에서의 최댓값을 갱신하면서 이동한다.

3. 최댓값이 갱신될 때마다 마지막에 도착한 점을 바꿔준다.

4. connect 값이 0이 될때마다 queue에 넣어줌으로서 탐색을 이어간다.

5. 1번 점에서의 최댓값과 경로를 출력한다.

 

 

문제 접근 방법 - 2번 + 3번 + 4번(find_route() 함수를 참고해주세요)

위의 설명을 코드로 짠 부분입니다.

x점에서 연결된 점들을 확인하고(xx점이라고 하겠습니다.) xx점에서의 최댓값과 경로를 계속 갱신해주면서 connect[xx]의 값을 -1 해줍니다.

이때 connect[xx]의 값이 0이 된다면 xx 점을 queue에 넣어줘서 탐색을 이어갑니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M;
int maxi[1001];
int connect[1001];
vector<pair<int, int>> line[1001];
vector<int> route[1001];

void find_route() {
	queue<int> q;
	q.push(1);
	route[1].push_back(1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < line[x].size(); i++) {
			int xx = line[x][i].first;
			int cnt = line[x][i].second;
			if (maxi[xx] < maxi[x] + cnt) {
				maxi[xx] = maxi[x] + cnt;
				route[xx] = route[x];
				route[xx].push_back(xx);
			}
			connect[xx]--;
			if (connect[xx] == 0) {
				q.push(xx);
			}
		}
	}
}

void solve() {
	find_route();
	cout << maxi[1] << "\n";
	for (int i = 0; i < route[1].size(); i++) {
		cout << route[1][i] << " ";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y, k;
		cin >> x >> y >> k;
		line[x].push_back(make_pair(y, k));
		connect[y]++;
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!