문제 이해 단계
https://www.acmicpc.net/problem/1238
N개의 마을에 연결된 M개의 단방향 도로가 존재한다.
각 도로에는 오고 가는 시간(비용)이 존재한다.
N개의 마을 중 특정 마을 X로 왕복해야 하는데,
어느 마을에서 출발하는 것이 가장 시간이 오래 걸리는가?
그때의 소요 시간을 구하는 출력하는 문제
문제 접근 단계
문제 유형 유추
N개의 마을에 연결된 M개의 단방향 도로라는 말을 읽자마자
바로 그래프 탐색이 떠올랐다.
마을을 정점으로 치환하고, 단방향 도로를 단방향 간선으로 본다.
그리고 걸리는 시간을 각 간선의 가중치로 보면 완벽한 그래프 탐색 문제이다.
로직
어쨌든 이 학생들은 무조건 최단 거리로 오고 간다고 했다.
그래프 탐색에서 최단거리라고 하면 생각나는 것이 크루스칼, 다익스트라 알고리즘이다.
해당 문제에서는 왕복을 해야 한다.
A정점에서 출발해서 X정점까지 간 다음, 다시 X 정점에서 A정점까지 돌아가야 한다.
한마디로 A → X 최단 거리와 X → A의 최단 거리가 필요하다.
여기서 다익스트라 알고리즘으로
정점 A에서 다른 경로로 가는 모든 최단 거리 비용과
정점 X에서 다른 경로로 가는 모든 최단 거리 비용을 구했다면?
왕복 거리 비용을 쉽게 구할 수 있을 것이다.
즉, 모든 노드에 대해 다익스트라 알고리즘을 수행해,
각 노드에서 다른 노드로 가는 최단거리 비용을 구하는 것이다.
이때 시간 복잡도는 우선순위큐로 구현할 경우
(간선의 수)*log(정점의 수) = 10,000*log1,000으로 1초가 넘지 않는다.
이를 이제 문제 구현 단계에서 코드로 구현해 보자.
문제 구현 단계
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 99999999
int N,M,X;
vector<pair<int,int>> v[1001]; // 마을과 간선 정보
int d[1001][1001] = {0,}; // 각 정점에서 다른 정점으로의 최소 비용 정보
// 다익스트라 알고리즘(매개변수 : 기준 정점)
void dijkstra(int num){
// 거리에 대해 내림차순 정렬(거리가 짧은것부터 뽑힘)
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
d[num][num] = 0;
q.push({0,num});
while(!q.empty()){
int x = q.top().second;
int distance = q.top().first;
q.pop();
// 연결된 간선
for(int i = 0; i < v[x].size(); i++){
int nx = v[x][i].first; // 연결된 마을
// 기존 시간 + 그 도로를 건너는데 드는 비용
int nDistance =distance + v[x][i].second;
// 기존에 것보다 거리가 짧으면 갱신
if(d[num][nx] > nDistance){
d[num][nx] = nDistance;
q.push({nDistance,nx});
}
}
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M >> X;
for(int i = 0; i < M; i++){
int v1,v2,v3;
cin >> v1 >> v2 >> v3;
v[v1].push_back({v2,v3});
}
fill(&d[0][0],&d[1000][1001],INF);
for(int i = 1; i <= N; i++) dijkstra(i);
int ans = 0;
for(int i = 1; i<= N; i++){
ans = max(ans,d[i][X]+d[X][i]);
}
cout << ans;
}핵심적으로 봐야 할 것은 dijkstra함수 부분이다.
매개변수로 기준이 되는 정점을 받는다.
그리고 최소거리를 저장하는 배열 d를 2차원으로 둔다.
여기서 아이디어는 다익스트라를 모든 정점에 대해 수행하는 것밖에 없기 때문에
딱히 코드에 대해서는 설명할 게 없을 것 같다.
시행착오
골드 3치고는 쉬웠던 문제 같다. 정확히는 다익스트라 알고리즘을 알고 있다면,
어렵지 않게 풀 수 있었던 문제 같다.
그래프 탐색 문제에 하도 데이다 보니까
이 문제는 40분 정도에 빨리 해결할 수 있었다.
야호
토스아이디
toss.me