화투의 개발 블로그

[문제 링크]

각 도시에서 한 도시로의 왕복 최단 거리 중에 최장 거리를 구하는 문제이다(?)

directed graph이기 때문에 X라는 도시에 갈 때와, X라는 도시에서 돌아 올 때의 경로는 둘 다 다르다.

난 이 문제를 3가지 방법으로 풀었다. 

.

1. 플로이드-와샬 알고리즘으로 전체 최단 경로를 구해 푸는 방법.

플로이드-와샬 알고리즘으로는 코드도 정말 간단하고,정답도 잘 나왔지만, 플로이드-와샬 자체가 O(n^3)인 알고리즘인지라 시간초과가 났다. 가지치기를 잘 하면 accept 되는거 같긴 한데, 그래도 다익스트라를 이용하는 것 보다는 느릴거란 생각이 들었다.(또 아무래도 정점의 갯수에 비헤 간선이 워낙 적기 때문이기도 한거같다.)

2. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 각 정점별로의 최단거리 또한 구해서 X까지 가는 방법.

모든 정점에 대해서 다익스트라 알고리즘을 사용해서 최대값을 구했다. 이건 accept가 뜨긴 떴다. 하지만 개인적으로 만족스럽지 않았다. 실행 속도도 속도지만, 굳이 각 정점에 대해서 최단 거리를 구할 필요가 있나 생각이 들었다. 

3. 다익스트라 알고리즘으로 X에서 출발하는 모든 최단 경로를 구한 뒤, 모든 간선을 뒤집어서 X에서 출발하는 정점을 구하는 방법.

일단 정방향으로 되어있는 인접리스트로 최단 경로를 구하고, 그다음 역방향으로 되어있는 인접리스트로 최단 경로를 구했다. 

그냥 간선만 방향을 바꿔주면 다른 모든 정점에서 X로 오는 정점을 구하는 것과 다를 게 없다. 따라서 2번과는 다르게 다익스트라 알고리즘을 단 2번만 사용해서 최대값을 구할 수 있다.

1. 플로이드-와샬 알고리즘으로 구현한 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 987654321
using namespace std;
int n, m, x;
vector<vector<int> > fw;
int main() {
    scanf("%d %d %d", &n, &m, &x);
    fw.resize(n + 1);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            fw[i].push_back(MAX);
            if (i == j) fw[i][j] = 0;
        }
    }
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        fw[u - 1][v - 1] = w;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                if (fw[k][j] > fw[k][i] + fw[i][j])
                    fw[k][j] = fw[k][i] + fw[i][j];
            }
        }
    }
    int ret = 0;
    for (int i = 0; i<n; i++)
        ret = max(ret, fw[i][x] + fw[x][i]);
    printf("%d", ret);
}

2. 다익스트라 알고리즘 N번으로 구현한 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
int ret[1001] = {0,};
void dijkstra(int x,int y) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=0; i<n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    } 
    if(y==x){
        for(int i = 0; i<n; i++) ret[i] = dist[i];
    }
    else{
        ret[x] += dist[y];
    }    
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u-1].push_back(make_pair(v-1, w));
    }
    dijkstra(x-1,x-1);
    for(int i=0; i<n; i++){
        if(i!=x)
            dijkstra(i,x);
    }
    int mv = 0;
    for(int i=0; i<n;i++) mv = max(mv,ret[i]);   
    printf("%d",mv);
}

3. 다익스트라 알고리즘 2번으로 구현한 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj1, adj2;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
int ret[1001] = {0,};
void dijkstra(int x, vector<vector<pair<int,int> > > adj) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=0; i<n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    } 
    for(int i = 0; i<n; i++) ret[i] += dist[i];  
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj1.resize(n + 1);
    adj2.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj1[u-1].push_back(make_pair(v-1, w));
        adj2[v-1].push_back(make_pair(u-1, w));
    }
    dijkstra(x-1,adj1);
    dijkstra(x-1,adj2);
    int mv = 0;
    for(int i=0; i<n;i++) mv = max(mv,ret[i]);   
    printf("%d",mv);
}

[문제 링크]

다익스트라 알고리즘을 사용하면 된다.

다익스트라 알고리즘에 대한 설명은 다음 포스트를 참조하자

http://hsp1116.tistory.com/42

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#define MAX 987654321
using namespace std;
vector<vector<pair<int, int> > > adj;
int n, m, x;
typedef pair<int, int> node;
struct cmp {
    bool operator()(node x, node y) {
        return x.second > y.second;
    }
};
void dijkstra(int x) {
    priority_queue<node, vector<node>, cmp> pq;
    vector<int> dist(n+1,MAX); dist[x] = 0;
    pq.push(make_pair(x,0));
    for(int i=1; i<=n;i++){
        if(i!=x) pq.push(make_pair(i,MAX));
    }
    while(!pq.empty()){
        int u = pq.top().first;
        int d = pq.top().second; pq.pop();
        if(d > dist[u]) continue;
        for(int i = 0; i<adj[u].size(); i++){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push(make_pair(v,dist[v]));
            }
        }       
    }
    for(int i = 1; i<=n; i++){
        printf(dist[i] == MAX? "INF\n": "%d\n",dist[i]);
    }
    
}
int main() {
    scanf("%d %d %d", &n, &m, &x);
    adj.resize(n + 1);
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(make_pair(v, w));
    }
    dijkstra(x);
}

그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다.

하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)

하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)

하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)

마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem)이다.

다익스트라 알고리즘은 여기서 두번째 방법으로, 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다.

간선들은 모두 양의 간선들을 가져야 한다.

다익스트라 알고리즘의 기본 로직은, 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다.

정점을 잇기 전까지는 시작점을 재외한 정점들은 모두 무한대 값을 가진다.

정점 A에서 정점 B로 이어지면, 정점 B가 가지는 최단 거리는 시작점부터 정점 A까지의 최단 거리 + 점A와 점B 간선의 가중치와, 기존에 가지고 있던 정점 B의 최단 거리중 작은 값이 B의 최단 거리가 된다.

1. 다익스트라 알고리즘 기본 로직

다음과 같은 그래프가 있다. 여기서 시작점은 5번 정점이라고 해보자.

여기서 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다.

여기서 경로가 가장 짧은 정점을 고른다. 여기선 5번 노드이다. 5번 노드와 연결되어있는 노드는 2,4번 노드이다.

먼저 2번노드부터 보자. 2번 노드의 최단 거리를 가지고있는 현재 최단거리(INF)와, 5번 노드의 최단거리(0) + 2번-5번의 가중치(4) 값 중 가장 작은 값으로 갱신한다. 즉, dist[2] = min(dist[2], dist[5] + adj[5][2])을 구한다 이는 min(INF,4)이므로 4가 된다.

4번 노드 또한 4번 노드의 최단 거리를 가지고있는 현재 최단거리(INF)와, 5번 노드의 최단거리(0) + 4번-5번의 가중치(2) 값 중 가장 작은 값으로 갱신한다.

즉, dist[4] = min(dist[4], dist[5] + adj[5][4])을 구한다. min(INF,2)이므로 2가 된다.

이제 나머지 정점 중에서 경로가 가장 짧은 정점을 고른다. 가장 짧은 거리를 가지고 있는 노드는 2의 길이를 가지고 있는 4번 노드이다. 

이제 4번 노드의 인접노드는 2,3번 노드이다.

2번 정점의 최단 거리를 가지고있는 현재 최단거리(4)와, 4번 정점의 최단거리(2) + 2번-4번의 가중치(1) 값 중 가장 작은 값으로 갱신한다.

즉, dist[2] = min(dist[2], dist[4] + adj[4][2])을 구한다

2번 정점의 기존 최단 거리 dist[2]는 4고, dist[4] + adj[4][2]는 3이므로 3으로 갱신된다.

또한 3번 정점은 의 최단 경로 dist[3]은 INF이므로, dist[4] + adj[4][3] = 3으로 갱신한다.

위와 같은 방법을 반복한다. 3,2번 정점의 최단 경로가 똑같으므로 숫자적으로 앞에 있는 2번 경로를 꺼내고, 인접 정점을 비교한다.

인접 정점은 1로 간선 가중치는 3이다. 따라서 dist[1] = min(dist[1], dist[2] + adj[2][1])을 구한다. dist[1]은 INF이므로, dist[2] + adj[2][1]인 6으로 갱신된다.

최단 경로가 3인 정점 3을 꺼내고 인접 정점을 비교한다. 인접 정점은 4다. dist[4] = min(dist[4], dist[3] + adj[3][4])를 계산한다.

dist[4] 는 2이고,dist[3] + adj[3][4]는 5이다. dist[4]가 더 작으므로 그대로 유지된다.

마지막으로 남은 정점은 1이다. 1을 꺼내고 인접 정점을 비교한다. 인접 정점은 3과 4다. 

dist[4] = min(dist[4], dist[1] + adj[1][4])를 계산한다.

dist[4] 는 2이고,dist[1] + adj[1][4]는 9이다. dist[4]가 더 작으므로 그대로 유지된다.

dist[3] = min(dist[], dist[6] + adj[6][3])를 계산한다.

dist[3] 는 3이고,dist[1] + adj[1][3]는 9이다. dist[4]가 더 작으므로 그대로 유지된다.

모든 정점을 방문했다. 완성한 테이블이 5번 정점부터 나머지 정점까지의 최단 경로이다.

2. 우선순위 큐(힙구조)를 이용한 다익스트라 알고리즘

위 방법은 배열을 매번 탐색해서 가장 짧은 거리를 찾는 방법이다.

하지만 힙 구조를 이용하면 더욱 빠른 시간 내에 구현이 가능하다.

최소 힙을 사용하면 가장 작은 경로를 가진 정점이 나오도록 구현하면 되기 때문이다.

그래프를 다시 한번 보자. 

모든 정점들을 힙(우선순위 큐)에 넣는다. 

dist배열

위 표에서 i는 정점 인덱스, d는 최단 거리이고 p는 이전 정점이다. d를 기준으로 최소 힙으로 구성한다.

힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 5이고 최소 거리가 0인 값이다.

기존에 있던 dist[5]와 d를 비교한다. dist[5]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

둘 다 0으로 같으므로, 5 주변의 인접 정점을 계산하고 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[2] = min(dist[2], dist[5] + adj[5][2], dist[4] = min(dist[4], dist[5] + adj[5][4])

dist배열

힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 4이고 최소 거리가 2인 값이다.

기존에 있던 dist[4]와 d를 비교한다. dist[4]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[4]는 2이고, d는 2로 같으므로,

4 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[2] = min(dist[2], d + adj[4][2], dist[3] = min(dist[3], d + adj[4][3]))

힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 2이고 최소 거리가 3인 값이다.

기존에 있던 dist[2]와 d를 비교한다. dist[2]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[2]는 3이고, d는 3으로 같으므로,

2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는 정점들을 큐에 넣는다.(dist[1] = min(dist[1], dist[2] + adj[2][1]))

dist배열

힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 3이고 최소 거리가 3인 값이다.

기존에 있던 dist[3]와 d를 비교한다. dist[3]가 더 작으면 연산하지 않고, 같거나 크면 연산한다.

dist[3]는 3이고, d는 3으로 같으므로,

2 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는정점들을 큐에 넣는다.(dist[4] = min(dist[4], dist[4] + adj[4][2]))

여기서 dist[4]는 2로 계산값보다 더 작으므로 큐에 넣지 않는다.

dist배열

힙에서 가장 위에 있는 값을 꺼낸다. 인덱스가 2이고 최소 거리가 4인 값이다.

dist[2]=3보다 d=4가  더 크므로 계산하지 않는다.

dist배열

기존에 있던 dist[1]와 d를 비교한다.dist[1]는 7이고, d는 7로 같으므로,

1 주변의 인접 정점을 계산해서 기존의 dist[i]보다 더 작아지는정점들을 큐에 넣는다.(dist[4] = min(dist[4], dist[1] + adj[1][4]),dist[3] = min(dist[3], dist[1] + adj[1][3]))

둘 다 기존의 dist[i]보다 크므로 큐에 넣지 않는다.

dist배열

큐에 남아있는 정점들은 전부 d가 INF로 dist[i]보다 크므로 계산되지 않는다.

이를 구현한 코드는 밑과 같다. 위에선 작성되어 있지 않지만 갱신 시마다 위의 정보들을 map에 넣어주면 경로를 쉽게 구할 수 있다. 

이 또한 코드에서 구현해보았다.

3. C++ 우선순위 큐 다익스트라 알고리즘 코드

#include <cstdio>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <utility>
#define MAX_VALUE -987654321
using namespace std;
int n, m, s;
class Vertex {
public:
    int index;
    int dist;
    int post = 0;
    Vertex(int index, int dist, int post) :index(index), dist(dist), post(post) {
    }
    Vertex(int index) :index(index) {
        dist = MAX_VALUE;
    }
    void setDist(int d) {
        dist = d;
    }
    bool operator >(const Vertex& v) const {
        return dist > v.dist;
    }
    bool operator <(const Vertex& v) const {
        return dist < v.dist;
    }
};
class Graph {
public:
    int n = 0;
    vector<Vertex> vt;
    vector<vector<pair<int, int> > > adj;
    priority_queue<Vertex > pq;
    map<int, pair<int, int> > m;

    void addVertex(int index, int dist) {
        vt.push_back(Vertex(index, dist, index));
        n = vt.size();
        adj.resize(n + 1);
    }
    void addVertex(int index) {
        vt.push_back(Vertex(index));
        n = vt.size();
        adj.resize(n);
    }
    void addAdj(int u, int v, int w) {
        adj[u - 1].push_back(make_pair(v, w));
    }
    void setStart(int index) {
        vt[index - 1].setDist(0);
        vt[index - 1].post = index;
    }
    void dijkstra(int s) {
        vector<int> dist(n, -1 * MAX_VALUE);
        dist[s - 1] = 0;
        setStart(s);
        for (int i = 0; i<n; i++) {
            pq.push(vt[i]);
        }
        m.insert(make_pair(s, make_pair(0, -1)));
        while (!pq.empty()) {
            int index = pq.top().index - 1;
            int cost = -1 * pq.top().dist; pq.pop();
            if (dist[index] < cost) continue;
            for (int i = 0; i<adj[index].size(); i++) {
                int n = adj[index][i].first;
                int v = adj[index][i].second;
                if (dist[n - 1] > dist[index] + v) {
                    dist[n - 1] = dist[index] + v;
                    Vertex newVt = Vertex(n, -dist[n - 1], index + 1);
                    pq.push(newVt);
                    m[n] = make_pair(dist[n - 1], index + 1);

                }
            }
        }

        printf("인덱스 별 최단 경로 길이\n");
        for (int i = 0; i<n; i++) {
            printf(dist[i] != -1 * MAX_VALUE ? "%d " : "INF ", dist[i]);
        }
        printf("\n\n인덱스 - 최단 경로 - 이전 정점\n");
        for (int i = 1; i <= m.size(); i++) {
            printf("%d - %d - %d\n", i, m[i].first, m[i].second);
        }
        printf("\n");
        for (int i = 1; i <= n; i++) {
            printf("%d까지 경로 : ", i);
            if (dist[i - 1] != -MAX_VALUE) {
                stack<int> st;
                int next = m[i].second;
                while (next != -1) {
                    st.push(next);
                    next = m[next].second;
                }
                while (!st.empty()) {
                    printf("%d - ", st.top());
                    st.pop();
                }
                printf("%d\n", i);
            }
        }
    }
};
int main() {
    scanf("%d %d %d", &n, &m, &s);
    Graph gp;
    for (int i = 0; i<n; i++) {
        gp.addVertex(i + 1);
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        gp.addAdj(u, v, w);
    }
    gp.dijkstra(s);
}

<실행 화면>