[C++] 백준 11779번 최소비용 구하기 2

11779번: 최소비용 구하기 2

다익스트라 문제.

BaaaaaaaaaaarkingDog 님의 0x1D강 - 다익스트라 알고리즘 에 수록된 문제이다.

특정 도시에서, 특정 목적지까지 최소 비용을 구할 뿐만 아니라 경로까지 출력해야 하는 문제.

 

문제 해석

어려운 조건은 없고 특정 도시에서 다른 도시까지 가는 데 최소 비용을 출력하면 된다.

이 때 최소 비용 뿐만 아니라, 해당 목적지까지 가는 경로도 출력해야 한다.

 

코드

 

/*
* 백준 11779번 최소비용 구하기 2
* https://www.acmicpc.net/problem/11779
* - 그래프 이론 / 다익스트라
*/
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct CurrentState {
	int curCost = 0;
	vector<int> pathCityVec;
};

int cityCnt, busCnt;
int start, destination;
bool visit[1001];
vector<vector<pair<int, int>>> adjVec(1001, vector<pair<int, int>>());
CurrentState endState;

struct comp {
	bool operator()(pair<CurrentState, int> c1, pair<CurrentState, int> c2) {
		return c1.first.curCost > c2.first.curCost;
	}
};

void go() {
	priority_queue<pair<CurrentState, int>, vector<pair<CurrentState, int>>, comp> pq;
	pq.push({ {0, {start}}, start});
	visit[start] = true;

	while (!pq.empty()) {
		CurrentState currentState = pq.top().first;
		int curNum = pq.top().second;
		pq.pop();
		visit[curNum] = true;

		//cout << curNum << "\n";
		//for (int i = 0; i < currentState.pathCityVec.size(); i++) {
		//	cout << currentState.pathCityVec[i] << ", ";
		//}
		//cout << "\n";

		if (curNum == destination) {
			endState = currentState;
			break;
		}

		for (int i = 0; i < adjVec[curNum].size(); i++) {
			int cost = adjVec[curNum][i].first;
			int nxtNum = adjVec[curNum][i].second;

			if (visit[nxtNum]) continue;

			CurrentState nxtState = currentState;
			nxtState.curCost += cost;
			nxtState.pathCityVec.push_back(nxtNum);
			pq.push({ nxtState, nxtNum });
		}
	}
}

int main() {
	cin >> cityCnt >> busCnt;

	int startCity, destCity, cost;
	for (int i = 1; i <= busCnt; i++) {
		cin >> startCity >> destCity >> cost;
		adjVec[startCity].push_back({ cost, destCity });
	}
	cin >> start >> destination;

	go();

	cout << endState.curCost << "\n";
	cout << endState.pathCityVec.size() << "\n";
	for (int i = 0; i < endState.pathCityVec.size(); i++) {
		cout << endState.pathCityVec[i] << " ";
	}

	return 0;
	
}

나 같은 경우, 다음과 같이 풀었다.

• 인접 리스트 형태로 그래프를 구현해 놓는다.
• 문제에서 도시 수, 버스 수, 버스의 정보와 출발지와 목적지를 입력 받는다.
• 우선순위 큐의 정렬 메서드를 구조체로 구현한 후, 비용이 가장 적은 경로먼저 탐색하도록 한다.
• 우선순위 큐에서 벡터를 통해 경로들도 같이 저장하도록 한다.
• 만일 현재 정점이 목적지라면, 현재 정점에 대한 정보들을 전역변수에 저장하고 결과를 출력한다.