[백준] 1238번 : 파티

🔗 문제 링크

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

---

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 마을 개수 n과 도로의 개수 m, 파티가 열리는 마을 x 를 입력 받아 저장한다.
=> 이 때 n은 노드 개수, m은 간선 개수, x는 시작 지점이자 도착 지점으로 볼 수 있다.

2) (다른 도시들에서 x 도시까지 가는 거리 + x 도시에서 다른 도시들로 가는 거리)를 저장하기 위해 result 배열을 선언한다.

3) 1 ~ n 도시에서 x 도시까지의 거리를 각각 구하기 위해 1 ~ n을 시작점으로하는 다익스트라 알고리즘을 각각 실행한다. (다익스트라 알고리즘 과정은 생략)

• 각 알고리즘을 실행하고 나면 dp[x]에 (현재 순서(i) 도시 ~ x 도시까지의 최단 거리)가 저장이 되므로, 이를 result[i]에 누적한다.
• 다익스트라 알고리즘 실행 전에 매번 dp 배열을 INF로 초기화해준다.

4) x 도시에서 1 ~ n 도시까지의 거리를 구하기 위해 x를 시작점으로 하는 다익스트라 알고리즘을 1회 실행한다.

• 알고리즘을 실행하고나면 dp[1 ~ n]에 각각 (x 도시에서 1 ~ n도시까지의 최단 거리)가 저장이되므로, 이를 result[1 ~ n]에 누적한다.
• 다익스트라 알고리즘 실행 전에 dp 배열을 INF로 초기화해준다.

5) 오고 가는 데에 시간이 가장 오래 걸리는 경우를 구해야하므로, result 배열에 들어있는 모든 값들을 탐색해 그 중 가장 큰 값을 출력한다.

---

🖥️ 풀이 코드

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

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> graph;
int dp[1001];
int result[1001];
int n, m, x;
const long long INF = 1e9;

void dijkstra(int start)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, start));
	dp[start] = 0;
	while (!pq.empty())
	{
		int dist = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (dp[cur] < dist)	continue;
		for (int i = 0; i < graph[cur].size(); i++)
		{
			pii curEdge = graph[cur][i];
			int cost = dist + curEdge.first;
			if (cost < dp[curEdge.second])
			{
				dp[curEdge.second] = cost;
				pq.push(pii(cost, curEdge.second));
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m >> x;
	graph.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(pii(c, b));
	}
	
	// 1 ~ n 도시부터 x 도시까지의 거리 구하기
	for (int i = 1; i <= n; i++)
	{
		fill(dp, dp + n + 1, INF);
		dijkstra(i);
		result[i] += dp[x];
	}

	// x 도시부터 1 ~ n 도시까지의 거리 구하기
	fill(dp, dp + n + 1, INF);
	dijkstra(x);
	for (int i = 1; i <= n; i++)
		result[i] += dp[i];

	int maxTime = 0;
	for (int i = 1; i <= n; i++)
	{
		if (maxTime < result[i])
			maxTime = result[i];
	}
	cout << maxTime;
}

---

✍️ 더 효율적인 풀이

• 위 코드의 경우 다익스트라 알고리즘이 n + 1회 실행된다. (다른 도시에서 x 도시까지의 최단 거리 구하기 위해 n회 + x 도시에서 다른 도시까지의 거리 구하기 위해 1회)
• 하지만 다른 도시에서 x 도시까지의 최단 거리를 구하는 데에 다익스트라 알고리즘을 1회만 실행할 수 있는 방법이 있다.
  • 모든 노드에서 특정 노드까지의 최단 거리
  • 기존 그래프의 역그래프에서 특정 노드에서 다른 모든 노드까지의 최단 거리
• 위 두 경우는 같은 결과값을 가지게 된다.
  첫 번째 경우는 모든 노드를 시작점으로 다익스트라 알고리즘을 n회 실행해야하지만, 두 번째 경우는 특정 노드를 시작점으로 다익스트라 알고리즘을 1회만 실행하면 되므로 시간적으로 더 효율적이다.
• 따라서 (기존 그래프에서 x를 시작점으로 하는 다른 모든 노드까지의 최단 거리) + (역 그래프에서 x를 시작점으로 하는 다른 모든 노드까지의 최단 거리)를 구하면 각 노드에서 x까지 갔다가 되돌아오는 거리를 구할 수 있다.

---

🖥️ 풀이 코드

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

using namespace std;
typedef pair<int, int> pii;

vector<vector<pii>> graph;
vector<vector<pii>> reverse_graph;
int dp[1001];
int result[1001];
int n, m, x;
const long long INF = 1e9;

void dijkstra(int start, bool reverse)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, start));
	dp[start] = 0;
	while (!pq.empty())
	{
		int dist = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (dp[cur] < dist)	continue;
		if (!reverse)
		{
			for (int i = 0; i < graph[cur].size(); i++)
			{
				pii curEdge = graph[cur][i];
				int cost = dist + curEdge.first;
				if (cost < dp[curEdge.second])
				{
					dp[curEdge.second] = cost;
					pq.push(pii(cost, curEdge.second));
				}
			}
		}
		else
		{
			for (int i = 0; i < reverse_graph[cur].size(); i++)
			{
				pii curEdge = reverse_graph[cur][i];
				int cost = dist + curEdge.first;
				if (cost < dp[curEdge.second])
				{
					dp[curEdge.second] = cost;
					pq.push(pii(cost, curEdge.second));
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m >> x;
	graph.resize(n + 1);
	reverse_graph.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(pii(c, b));
		reverse_graph[b].push_back(pii(c, a));
	}

	// 1 ~ n 도시부터 x 도시까지의 거리 구하기
	fill(dp, dp + n + 1, INF);
	dijkstra(x, true);
	for (int i = 1; i <= n; i++)
		result[i] += dp[i];

	// x 도시부터 1 ~ n 도시까지의 거리 구하기
	fill(dp, dp + n + 1, INF);
	dijkstra(x, false);
	for (int i = 1; i <= n; i++)
		result[i] += dp[i];

	int maxTime = 0;
	for (int i = 1; i <= n; i++)
	{
		if (maxTime < result[i])
			maxTime = result[i];
	}
	cout << maxTime;
}