BOJ 1238

21 Apr 2020 • ProblemSolving

파티

문제출처

문제 해석

  • N명의 학생이 X번 마을에 갔다가 집으로 돌아오는데 최단시간을 오고 간다고 했을 때, 가장 많은 시간을 소비하는 학생이 누구인지 구하는 문제입니다.
  • 각 마을 사이에는 총 M개의 단방향 도로들이 있고, 도로마다 소비되는 시간이 정해져 있습니다.

설계(10)

  • 최단거리를 구하는 문제로 다익스트라 알고리즘을 사용해야 할 것으로 보입니다.
  • 플로이드-와샬 알고리즘은 O(N^3)으로 시간초과가 날것으로 보이기 때문에 사용하지 않습니다.
  • 우선, 각 마을에서 X번마을로 이동하는데 걸리는 최단시간과, X번 마을에서 다른 마을로 이동하는데 걸리는 최단시간 두개를 모든 마을에 대해서 탐색하는 경우를 생각할 수 있습니다.
  • 이는 O(NxMx2log(N))=O(NMlogN)정도로, 1억에 가까운 시간복잡도가 되어서 가능은 할 것으로 보입니다.
  • 문제의 의도는 위의 구현방법이 정해가 아닌 것 같아서 더 최적화가 필요했습니다.
  • 주어지는 문제에서 모든 간선은 단방향으로, 정해진 방향의 반대방향을 가지는 그래프를 구하면, 모든 마을에서 X마을로 오는데 걸리는 최단시간을 구할 수 있습니다.
  • 또한, 정해진 그래프를 이용하여 X에서 시작하여 다른 모든 마을로 가는데 걸리는 최단시간을 구하면 모든 경로의 최단시간을 구할 수 있습니다.
  • 역방향 그래프를 이용한 최단거리 + 정방향 그래프를 이용한 최단거리의 최댓값을 구하면 원하는 값을 구할 수 있게 됩니다.
  • 이 방법은 단 2번의 다익스트라 알고리즘 사용으로 구할 수 있기 때문에 O(MlogN)의 시간복잡도가 들게 됩니다.

구현(40)

코드1 (NMlogN)
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 1001
vector<pair<int,int> > adj[MAXN];

int dist[MAXN];
struct node{
    int cur,w;
    bool operator < (const node& a)const{
        return a.w < w;
    }
};
priority_queue<node> pq;
int N,M,X;
int dijkstra(int start, int end){
    memset(dist,-1,sizeof(dist));
    while (!pq.empty()) pq.pop();
    pq.push({start,0});
    dist[start] = 0;
    while (!pq.empty()){
        int cur = pq.top().cur;
        int cur_w = pq.top().w;
        pq.pop();
        if (dist[cur] != cur_w) continue;
        if (cur == end) return cur_w;
        for (int i = 0 ;i < adj[cur].size(); i++){
            int next = adj[cur][i].first;
            int next_w = adj[cur][i].second+cur_w;
            if (dist[next]==-1 || dist[next]>next_w){
                dist[next] = next_w;
                pq.push({next,dist[next]});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> X;
    memset(dist,-1,sizeof(dist));
    while (M--){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
    }
    int ans = 0;
    for (int i = 1; i<=N; i++){
        ans = max(ans,dijkstra(i,X)+dijkstra(X,i));
    }
    cout << ans <<"\n";
    return 0;
}
코드2 (MlogN)
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 1001
vector<pair<int,int> > adj1[MAXN];
vector<pair<int,int> > adj2[MAXN];
int dist1[MAXN];
int dist2[MAXN];

priority_queue<pair<int,int> > pq;
int N,M,X;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> X;
    memset(dist1,-1,sizeof(dist1));
    memset(dist2,-1,sizeof(dist2));
    while (M--){
        int u,v,w;
        cin >> u >> v >> w;
        adj1[u].push_back({v,w});
        adj2[v].push_back({u,w});
    }
    pq.push({0,X});
    dist1[X] = 0;
    while (!pq.empty()){
        int cur = pq.top().second;
        int cur_w = -pq.top().first;
        pq.pop();
        for (int i = 0 ;i < adj1[cur].size(); i++){
            int next = adj1[cur][i].first;
            int next_w = adj1[cur][i].second+cur_w;
            if (dist1[next]==-1 || dist1[next]>next_w){
                dist1[next] = next_w;
                pq.push({-dist1[next],next});
            }
        }
    }
    pq.push({0,X});
    dist2[X] = 0;
    while (!pq.empty()){
        int cur = pq.top().second;
        int cur_w = -pq.top().first;
        pq.pop();
        for (int i = 0 ;i < adj2[cur].size(); i++){
            int next = adj2[cur][i].first;
            int next_w = adj2[cur][i].second+cur_w;
            if (dist2[next]==-1 || dist2[next]>next_w){
                dist2[next] = next_w;
                pq.push({-dist2[next],next});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <=N; i++){
        ans = max(ans,dist1[i] + dist2[i]);
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 코드1 : 116 ms, 코드2: 0 ms

마무리

  • 다익스트라 알고리즘의 응용문제였습니다. 문제의 정해를 구하기 위해서는 약간의 아이디어가 필요합니다.
 BOJ

Related Posts