[C++] 백준/BOJ - 1719 : 택배 ( 다익스트라 풀이 )

---

문제 이해 단계

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

1719번: 택배

n개의 정점과 m개의 간선이 존재한다.
그리고 간선 사이에는 가중치가 존재한다.

모든 정점에서 다른 정점으로의 경로표를 만들어야 한다.

한 정점에서 다른 정점으로 최단경로로 움직일 때, 거쳐야 하는 다른 정점을 경로표에 적어 넣는다.
그리고 경로표 전체를 출력하는 것이 해당 문제이다.

 

---

문제 접근 단계

---

로직 유추

문제를 보면 바로 정점과 간선이 있는 그래프를 준다.
이 점을 보니 바로 그래프 탐색 문제라는 것을 쉽게 알 수 있다.

어쨌든 구해야 하는 것은 최단경로
그래프에서 최단 경로하면 떠오르는 것이 다익스트라 알고리즘이다.

나는 해당 문제를 다익스트라 알고리즘으로 접근하였다.

다익스트라는 한 정점에서 다른 모든 정점으로의 최단경로를 보는 것이지만,
경로표를 채우기 위해서는 모든 정점에 대해 다 검사해줘야한다.

그래서 최소 거리를 저장하는 배열을 2차원 배열로 선언해 주기로 했다.
그리고 각 정점을 시작점으로 하는 다익스트라 알고리즘을 한 번씩 다 진행시켜 줬다.

---

경로 추적

결론적으로 구해야 하는 것은 최단 경로가 아닌,중간에 거쳐가는 정점이다.

이걸 어떤 식으로 구해야 할지 생각하다가
arr [시작 정점][도착 정점] = 직전에 방문한 정점
을 뜻하는 2차원 배열을 만들어 경로 정보를 추적하도록 하였다.

문제에서 준 그림

예를 들어 정점 1에서 시작했다고 가정해 보자.
정점 5로 간다고 생각해 보자.

정점 1에서 정점 5까지 가는데 최단거리가 되려면 정점 2를 들러야 한다.
즉 arr [1][5] = 2가 된다는 뜻이다.

이런 식으로 경로를 추적한다.

다익스트라 알고리즘은 문제 구현 단계에서 코드로 자세히 보도록 한다.

 

---

문제 구현 단계

int n,m;
int d[201][201]; // 시작 정점별 최단 거리를 담을 배열
vector<pair<int,int>> v[201];
int trace[201][201]; // 시작 정점별 경로 추절
void dijkstra(int num){
    // 우선순위 큐 내림차순 정렬(거리가 짧은게 먼저 뽑히게끔함)
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

    d[num][num] = 0; // 자기 자신 거리 0
    q.push({0,num});

    // 초기화 -> 정점 자기 자신
    for(int i = 0; i < 200; i++) trace[num][i] = i;

    
    while(!q.empty()){
        int distance = q.top().first;
        int x = q.top().second; // 중간 경로
        q.pop();
        for(int i = 0; i < v[x].size(); i++){
            int next = v[x][i].first; // 중간 경로와 연결된 도착 경로

            // 해당 중간 경로를 통해 시작 경로 ~ 도착 경로를 했을 때 드는 거리 비용
            int nextDistance = distance+v[x][i].second;
            if(d[num][next] > nextDistance){
                // 기존에 저장되어있던 값보다 작으면 바꿔줌
                d[num][next] = nextDistance;
                q.push({nextDistance,next});
                trace[num][next] = x; // 해당 중간 거리를 넣어줌
            }
        }
    }
}

다익스트라 알고리즘이다. 매개변수로 출발 정점을 받는다.

우선순위 큐를 사용하여 다익스트라를 구현하는데,
우선순위큐는 내림차순으로 정렬하여 거리가 짧은 원소가 먼저 나오게끔 하였다.

그리고 trace 정보를 초기화할 때 자기 자신의 정점 값을 초기화한다.

이는 출발 정점 ~ 도착 정점이 중간 정점을 거치지 않고 바로 도착할 때
도착 정점이 저장되게 하기 위해서이다.

그 안에 있는 것은 해당 중간 경로를 통해

갔을 때의 거리와 기존에 저장되어 있던 값을 비교하여, 최단 경로 값을 경신하는 것을 반복한다.

for(int i = 1; i<= n; i++){
    for(int j = 1; j <= n; j++){
        if(i == j) cout << "- ";
        else cout << trace[j][i] << " ";
    }
    cout << endl;
}

해당 코드는 다익스트라를 통해 trace를 모두 저장해 둔 값을 출력한다.

근데 이상하게 trace [i][j]로 출력하니까 의도한 거와는 y = x 축으로 반전된 상태로 나오더라..

그래서 꼼수를 써서 그 값들을 뒤집어서 정답을 얻어냈다...
사실 이 방법을 제외하곤 생각이 들지 않더라..

다른 사람들은 플루이드워셜 알고리즘 쓰던데..
이거 왜 안되는지 아시는 분..

일단 아래에 전체 코드를 올려두겠다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 99999999

int n,m;
int d[201][201]; // 시작 정점별 최단 거리를 담을 배열
vector<pair<int,int>> v[201];
int trace[201][201]; // 시작 정점별 경로 추절
void dijkstra(int num){
    // 우선순위 큐 내림차순 정렬(거리가 짧은게 먼저 뽑히게끔함)
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

    d[num][num] = 0; // 자기 자신 거리 0
    q.push({0,num});

    // 초기화 -> 정점 자기 자신
    for(int i = 0; i < 200; i++) trace[num][i] = i;

    
    while(!q.empty()){
        int distance = q.top().first;
        int x = q.top().second; // 중간 경로
        q.pop();
        for(int i = 0; i < v[x].size(); i++){
            int next = v[x][i].first; // 중간 경로와 연결된 도착 경로

            // 해당 중간 경로를 통해 시작 경로 ~ 도착 경로를 했을 때 드는 거리 비용
            int nextDistance = distance+v[x][i].second;
            if(d[num][next] > nextDistance){
                // 기존에 저장되어있던 값보다 작으면 바꿔줌
                d[num][next] = nextDistance;
                q.push({nextDistance,next});
                trace[num][next] = x; // 해당 중간 거리를 넣어줌
            }
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 0; i < m; i++){
        int v1,v2,v3;
        scanf("%d %d %d",&v1,&v2,&v3);
        v[v1].push_back({v2,v3});
        v[v2].push_back({v1,v3});
    }
    
    fill(&d[0][0],&d[200][201],INF);

    for(int i = 1; i <= n; i++){
        dijkstra(i);
    }
    for(int i = 1; i<= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) cout << "- ";
            else cout << trace[j][i] << " ";
        }
        cout << endl;
    }
}

 

---

시행착오

다익스트라인 건 금방 알았고, 경로 연결 전까지는 완벽하게 했다.
근데 경로 연결이 안 돼서 1시간 안에 못 풀었던 것 같다.

마지막에 결국엔 꼼수 써서 풀어서 약간 찜찜하다.
플루이드 워셜 알고리즘.. 알긴 해야겠다.

https://toss.me/howudong

howudong님에게 보내주세요