Notice
Recent Posts
Recent Comments
Link
궤도
[백준] 1238번 : 파티 본문
문제
풀이
처음에는 이 문제가 당연히 플로이드-워셜 문제인 줄 알았다... 실제로 그걸로 풀었더니 맞기도 했고...
근데 다익스트라 문제라는 것이다...!
난 이해가 되지 않았다. 다익스트라는 하나의 시작점에서 모든 정점과의 거리를 구하는 SSP 알고리즘인데
이 문제는 모든 사람에 대해 도착지점 하나에 대한 거리를 구해야 하기 때문이다...
굳이 모든 정점에 대해 하나하나 다익스트라를 돌리느니 플로이드-워셜이 낫지 않나 했는데
다익스트라 2번으로 해결할 수 있는 방법이 있었다.
이 분의 풀이를 봤다. 정말 생각도 못한 방법이었다.
플로이드-워셜로 푼 코드가 아깝기도 하니 둘 다 올리도록 하겠다.
소스코드 - 플로이드-워셜
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
vector<vector<int>> dist;
void floydWarshall() { //플로이드-워셜
int size = dist.size();
for (int i = 1; i < size; i++) {
for (int j = 1; j < size; j++) {
for (int k = 1; k < size; k++)
dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
}
}
}
int main() { //풀리긴 했는데 플로이드-워셜로 푸는 문제가 아니라고 함
int N, M, X, s, d, w;
cin >> N >> M >> X;
dist.assign(N + 1, vector<int>(N + 1, INF));
for (int i = 1; i <= N; i++) //자기 자신과의 거리는 0
dist[i][i] = 0;
for (int i = 0; i < M; i++) { //거리 초기 입력
cin >> s >> d >> w;
dist[s][d] = w;
}
floydWarshall();
int max_dist = 0;
for (int i = 1; i <= N; i++) //i-X-i의 거리 중 최댓값 구하기
max_dist = max(max_dist, dist[i][X] + dist[X][i]);
cout << max_dist;
}
플로이드-워셜의 전체 소스코드다.
그냥 반복문을 3번 도는거라 코드 자체는 짧다. dist 배열을 갱신하고 나면
i->X로 가는 dist와 X->i로 가는 dist를 더하며 최댓값을 갱신한다.
소스코드 - 다익스트라
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> pp;
const int INF = 1e9;
vector<int> min_dist; //최단 거리
vector<int> result; //결과
void dijkstra(int start, vector<vector<pp>> graph) {
priority_queue<pp, vector<pp>, greater<pp>> pq; //min-heap
int size = graph.size();
min_dist.assign(size, INF); //최단 거리 초기화
min_dist[start] = 0; //시작점의 거리는 0
pq.push(make_pair(0, start));
while (!pq.empty()) {
int cur_dist = pq.top().first; //시작점부터 cur 까지의 최단 거리
int cur = pq.top().second; //현재 정점
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) { //연결된 정점에 대해
int new_dist = cur_dist + graph[cur][i].second; //cur을 거쳐서 온 거리
if (new_dist < min_dist[graph[cur][i].first]) { //이게 현재의 graph[cur][i]의 최단 거리보다 짧다면
min_dist[graph[cur][i].first] = new_dist; //갱신
pq.push(make_pair(new_dist, graph[cur][i].first)); //큐에 넣기
}
}
}
}
int main() {
int N, M, X, s, d, w, max_result = 0;
vector<vector<pp>> graph; //입력 그래프
vector<vector<pp>> r_graph; //역방향 그래프
cin >> N >> M >> X;
graph.assign(N + 1, vector<pp>(0));
r_graph.assign(N + 1, vector<pp>(0));
result.assign(N + 1, 0);
for (int i = 0; i < M; i++) {
cin >> s >> d >> w;
graph[s].push_back(make_pair(d, w));
r_graph[d].push_back(make_pair(s, w));
}
dijkstra(X, graph); //X에서 집으로 돌아감
for (int i = 1; i <= N; i++)
result[i] = min_dist[i];
dijkstra(X, r_graph); //집에서 X로 감
for (int i = 1; i <= N; i++) {
result[i] += min_dist[i];
max_result = max(max_result, result[i]); //최댓값 갱신
}
cout << max_result;
}
다익스트라의 전체 소스코드다.
vector<vector<pp>> graph; //입력 그래프
vector<vector<pp>> r_graph; //역방향 그래프
먼저 그래프를 2개 만들고
for (int i = 0; i < M; i++) {
cin >> s >> d >> w;
graph[s].push_back(make_pair(d, w));
r_graph[d].push_back(make_pair(s, w));
}
연결 관계를 입력한다.
dijkstra(X, graph); //X에서 집으로 돌아감
for (int i = 1; i <= N; i++)
result[i] = min_dist[i];
dijkstra(X, r_graph); //집에서 X로 감
for (int i = 1; i <= N; i++) {
result[i] += min_dist[i];
max_result = max(max_result, result[i]); //최댓값 갱신
}
그리고 X에서 집으로 돌아가는 경로와 집에서 X로 가는 경로를 구해서 더하는데
void dijkstra(int start, vector<vector<pp>> graph) {
priority_queue<pp, vector<pp>, greater<pp>> pq; //min-heap
int size = graph.size();
min_dist.assign(size, INF); //최단 거리 초기화
min_dist[start] = 0; //시작점의 거리는 0
pq.push(make_pair(0, start));
while (!pq.empty()) {
int cur_dist = pq.top().first; //시작점부터 cur 까지의 최단 거리
int cur = pq.top().second; //현재 정점
pq.pop();
for (int i = 0; i < graph[cur].size(); i++) { //연결된 정점에 대해
int new_dist = cur_dist + graph[cur][i].second; //cur을 거쳐서 온 거리
if (new_dist < min_dist[graph[cur][i].first]) { //이게 현재의 graph[cur][i]의 최단 거리보다 짧다면
min_dist[graph[cur][i].first] = new_dist; //갱신
pq.push(make_pair(new_dist, graph[cur][i].first)); //큐에 넣기
}
}
}
}
코드는 그냥 평범한 다익스트라다.
여기 있는 코드와 유사한데
생각해보니 왜 visited 변수를 넣었는지 모르겠다.
당연히 이미 방문한 노드면 최단 경로가 갱신되지 않을테니 굳이 넣을 필요가 없는데...암튼 그래서 그 부분은 뺐다.
Comments