[백준 / C++] 파티 (골드3, 1238)

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

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

예제 출력 1

10

---

문제 풀이

이번 문제는 가중치가 존재하는 그래프에서 특정 위치 X까지 왕복으로 걸리는 시간이 가장 긴 시간을 찾는 문제입니다.

 

위와 같이 가중치가 주어진 그래프에서 경로를 탐색하는 문제는 다익스트라 알고리즘으로 쉽게 해결이 가능하며, 일반적으로 노드별로 가장 가까운 노드로 탐색을 이어 나가기에 우선순위 큐를 사용해 해결 시간을 줄이는 방식으로 해결하게 되었습니다.

 

우선 문제를 해결하기 위해서 모든 지점으로부터 X까지 가는 경로를 저장해야 합니다.

즉, for(i = 0 ~ N)까지 순회하며 거리를 체크해야 하므로 간단한 방문 배열을 만들어주도록 합니다.

 

이제 전체적으로 순회를 할 예정인데, 앞서 이야기했던 것처럼 다익스트라 알고리즘은 현재 노드에서 가장 최단의 거리로만 진출해가며, 방문했던 노드는 다시 방문하지 않는다는 특징을 가지고 있습니다.

 

여기서, 현재 노드에서 가장 최단의 노드를 빠르게 찾기 위해 우선순위 큐가 사용이 되며, 전체적인 로직은 BFS와 유사합니다.

 

위 코드를 보면 visited가 2차원 배열로 선언되어 있는데, 우선은 num이 들어가는 칸은 무시하고 설명해보도록 하겠습니다.

1. 현재 노드(U)에서 (U)까지의 거리는 0입니다. 거리를 초기화해주도록 합니다.
2. 우선순위 큐를 만들고, U와 U에서 U까지의 거리를 저장해주도록 합니다.
   • 여기서 우선순위 큐는 (노드, 노드까지의 거리)를 저장하며 노드까지의 거리가 최단인 순서를 우선적으로 체크하도록 설정하였습니다.
3. BFS와 마찮가지로 우선순위 큐가 빌 때까지 순회합니다.
   • 큐의 내용을 꺼내 현재 노드(U)까지의 거리(dist)가 기존에 저장된 거리(visited[current])보다 작은지 체크합니다.
     • 현재 노드까지의 거리(dist)가 더 큰 경우 이미 기존에 최적화된 길이 존재한다는 의미로 종료합니다.
   • 다음으로 현재 노드(U)와 연결된 길들을 순회하며 새로운 거리(현재 노드까지의 거리 + 다음 노드까지의 거리)를 업데이트 합니다.(visited 배열 업데이트)
   • 만약 기존의 거리(visited)보다 새로 구한 거리(newDistance)가 더 짧다면 우선순위 큐에 노드(도착 노드, 도착 노드까지의 거리)를 추가해주도록 합니다.

위 과정이 종료되면 i번째 노드로부터 0 ~ N 번째 노드까지의 최단 경로가 visited 배열에 저장되게 됩니다.

 

즉, for문을 순회하며 위 과정을 0 ~ N번째 노드까지 반복하며 X까지 가장 먼 노드를 찾기 위해 visited 배열을 2차원 배열로 선언해 사용하였으며 이렇게 하는 순간 최대 왕복 시간을 다음과 같이 구할 수 있게 됩니다.

 

이전 문제에서 다익스트라로 뻘짓을 많이해서인지 골드3 난이도 치고 생각보다 쉽게 풀이가 가능했던 문제였습니다.

(이전에 뻘짓했던 문제)

https://apth1023.tistory.com/144

[백준 / C++] 최단경로 (골드4, 1753)

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 987654321;
const int SIZE = 1002;

int n, m, x;
vector<pair<int, int>> adj[SIZE];
int visited[SIZE][SIZE];

struct Comp
{
	bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
	{
		return p1.second > p2.second;
	}
};

void BFS(int u, int num)
{
	visited[num][u] = 0;

	priority_queue <pair<int, int>, vector<pair<int, int>>, Comp> pq;
	pq.push(make_pair(u, 0));

	while (!pq.empty())
	{
		int dist = pq.top().second;
		int current = pq.top().first;
		pq.pop();

		// 이미 최적화된 길인 경우
		if (visited[num][current] < dist) continue;

		// 연결된 모든 길 순회
		for (int i = 0; i < adj[current].size(); i++)
		{
			// 거리 체크
			int newDistance = visited[num][current] + adj[current][i].second;

			if (visited[num][adj[current][i].first] > newDistance)
			{
				visited[num][adj[current][i].first] = newDistance;
				pq.push(make_pair(adj[current][i].first, newDistance));
			}
		}
	}
}

int main()
{
	cin >> n >> m >> x;

	for (int i = 0; i < m; i++)
	{
		int s, e, c;
		cin >> s >> e >> c;

		adj[s].push_back(make_pair(e, c));
	}

	for (int i = 0; i < SIZE; i++)
		fill(visited[i], visited[i] + SIZE, MAX);

	for (int i = 1; i <= n; i++)
		BFS(i, i);

	int mx = -1;
	for (int i = 1; i <= n; i++)
		mx = max(visited[i][x] + visited[x][i], mx);

	cout << mx;
}