백준 1238 - 파티(C++)

문제

N개의 정점이 있고 각 정점에서 특정 점정 X가 정해진다. 이때 각 정점에서 i를 방문하고 다시 자기 자신의 정점으로 돌아오는 최소 길이를 구한 뒤 가장 많은 비용을 소비하는 정점을 구하는 문제이다.

입력

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), X가 공백dmfh rnqnsehldj dlqfurehlsek.

두 번째 줄부터 M + 1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 T가 들어온다.

예시

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력

10

문제 해결

어디서 힌트를 얻을 수 있을까?

 

위의 문제를 처음 봤을 때 정점과 간선 그리고 최소 비용이라는 키워드를 통해서 그래프 탐색 문제라는 것을 알 수 있었다.

 

하지만 내가 아는 BFS를 적용하기에는 방문했던 노드를 또 들릴 수도 있다는 가능성 때문에 적용을 할 수가 없었다.

 

그렇다고 DFS를 적용하기에는 각 정점에서 도착 정점 까지의 거리와 도착 정점에서 각 정점까지의 거리를 일일이 구해야 하는데 이렇게 되면 시간 복잡도가 O(n^3)이 되기 때문에 시간을 초과할 것 같았다.

 

그렇게 고민을 하던 중 다익스트라라는 알고리즘을 접하게 되었다.

 

다익스트라 알고리즘은 간단하게 말해서 주어진 정점에서 각 정점 까지의 최단 거리를 구할 수 있는 알고리즘이다.

 

그러면 기존에 입력 받았던 간선을 두 가지 방법으로 받기로 했다.

1. 간선을 역으로 받는 방법
   
   이 방법을 이용하여 다익스트라 알고리즘을 적용하게 된다면 도착해야 할 정점 X를 시작 노드로 입력하여 사실상 각 정점에서 X에 도착하는 최소 비용을 구할 수 있게 된다.
2. 간선을 그대로 받는 방법
   
   이 방법을 이용하여 다익스트라 알고리즘을 적용하게 된다면 정점 X에서 각 정점까지 도착하는 최소 비용을 구할 수 있다.

위의 두 방법을 구한 뒤 더하고 그 중 최대 비용을 구하면 이 문제를 해결할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>

struct Node {
	int idx;
	int dis;
};

struct cmp {
	bool operator()(std::pair<int, int> a, std::pair<int, int> b)
	{
		if (a.second > b.second)
			return true;
		else if (a.second == b.second)
		{
			if (a.first > b.first)
				return true;
			else
				return false;
		}
		return false;
	}
};

int INF = 999999;
std::vector<Node> varr[2][1001];
int disArr[2][1001];


void Dijkstra(int flag, int Node)
{
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp> pqarr;
	pqarr.push(std::make_pair(Node, 0));
	disArr[flag][Node] = 0;
	int tmpNode;
	int tmpDis = 0;
	while (!pqarr.empty())
	{
		tmpNode = pqarr.top().first;
		tmpDis = pqarr.top().second;
		pqarr.pop();
		if (tmpDis > disArr[flag][tmpNode])
			continue;
		for (int i = 0; i < varr[flag][tmpNode].size(); i++)
		{
			int nextNode = varr[flag][tmpNode][i].idx;
			int nextDis = varr[flag][tmpNode][i].dis;
			if (disArr[flag][nextNode] > tmpDis + nextDis && nextNode != Node)
			{
				disArr[flag][nextNode] = tmpDis + nextDis;
				pqarr.push(std::make_pair(nextNode, disArr[flag][nextNode]));
			}
		}
	}
}

void init(void)
{
	for (int i = 0; i < 1001; i++)
	{
		disArr[0][i] = INF;
		disArr[1][i] = INF;
	}
}

int main(void)
{
	int N, M, X;
	std::cin >> N >> M >> X;

	for (int i = 0; i < M; i++)
	{
		int S, D, T;
		std::cin >> S >> D >> T;
		varr[0][D].push_back({S, T});
		varr[1][S].push_back({D, T});
	}
	init();
	Dijkstra(0, X);
	Dijkstra(1, X);
	int ret = 0;
	for (int i = 1; i <= N; i++)
	{
		if (i != X)
			ret = std::max(ret, disArr[0][i] + disArr[1][i]);
	}
	std::cout << ret << std::endl;
	return 0;
}

문제 출처

https://www.acmicpc.net/problem/1238

1238번: 파티

이론

https://deulee.tistory.com/10

다익스트라(Dijkstra) 알고리즘