백준 1719번 택배 (C++)

문제 링크 : https://www.acmicpc.net/problem/1719

1719번: 택배

문제 요약

 

1. 두 수 n과 m이 주어집니다.

2. n은 집하장의 개수 (200이하 자연수) 이며, m은 집하장간 경로의 개수 (1000이하 자연수) 입니다. 집하장간 경로의 소요 시간은 모두 1000이하의 자연수 입니다.

3. 1번부터 n번까지, 한 집하장에서 다른 집하장으로 최단 경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 출력하세요.

위 : 지도 예시 / 아래 : 정답 출력 예시

 

 

핵심 포인트

 

우선 다익스트라의 개념을 활용해 집하장간의 최단거리를 구해야합니다.

그런 다음 한 집하장에서 다른 집하장으로 화물을 이동시키기 위해 거쳐야하는 최초의 집하장을 구해야합니다.

이는 다익스트라의 개념을 잘 이해하고 있으면 해결할 수 있습니다.

 

문제 풀이

 

최단거리를 구하는 공식은 일반 다익스트라 알고리즘과 동일하므로 설명을 패스하도록 하겠습니다.

대신 한 집하장에서 다른 집하장으로 화물을 이동시키기 위해 거쳐야하는 최초의 집하장을 구하는 방법만 요약하여 작성하도록 하겠습니다.

 

아래는 1번부터 n번까지 집하장에서 다른 집하장으로 이동하기 위한 최단거리를 구하는 다익스트라 알고리즘입니다.

int ans[201][201]; // 최단거리
int stp[201][201]; // 최초로 거치는 집하장
 
 
void delivery(int from) {
    for (int i = 1; i <= n; i++) ans[from][i] = MAX, stp[from][i] = MAX; // 초기화
    ans[from][from] = 0; // 시작저짐만 0으로 초기화
    stp[from][from] = 0; // 시작지점만 0으로 초기화
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0,from });
    while (!pq.empty()) {
        dis = pq.top().first; // first 는 누적 거리
        pos = pq.top().second; // second는 현 위치
        pq.pop(); 
        for (int i = 0; i < map[pos].size(); i++) {
            npos = map[pos][i].first;
            ndis = map[pos][i].second;
            if (ans[from][npos] > ans[from][pos] + ndis) {
                ans[from][npos] = ans[from][pos] + ndis;
                if(stp[from][pos]==0) stp[from][npos] = npos; // 1
                else stp[from][npos] = stp[from][pos]; // 2
                pq.push({ ans[from][npos],npos });
            }
        }
    }
}

(1) 만약 stp[from][pos]가 0일 경우, 이는 현재 최초의 출발지점 from에서 시작하여 다음 집하장으로 갔음을 뜻합니다.

이 경우에는 stp[from][npos]는 npos로 저장하면 됩니다. 

예시로 시작지점인 1번 집하장에서 2번 집하장으로 가는 경우, 2번 집하장을 가기위해 최초로 거지는 지점은 (시작지점을 제외하고) 2번 집하장이기 때문입니다.

(2) 만약 stop[from][pos]가 0이 아닐 경우, 이미 최초의 지점이 결정되어있음을 뜻합니다. 이 경우 stp[from][npos]의 값은 stp[from][pos]의 값으로 저장하면 됩니다.

 

[전체 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
int n, m, dis, pos, ndis, npos; // n = 1번부터 n번까지 집하장 개수
vector<pair<int, int>> map[201];
int ans[201][201];
int stp[201][201];
 
 
void delivery(int from) {
    for (int i = 1; i <= n; i++) ans[from][i] = MAX, stp[from][i] = MAX;
    ans[from][from] = 0;
    stp[from][from] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0,from });
    while (!pq.empty()) {
        dis = pq.top().first; // first 는 누적 거리
        pos = pq.top().second; // second는 현 위치
        pq.pop(); 
        for (int i = 0; i < map[pos].size(); i++) {
            npos = map[pos][i].first;
            ndis = map[pos][i].second;
            if (ans[from][npos] > ans[from][pos] + ndis) {
                ans[from][npos] = ans[from][pos] + ndis;
                if(stp[from][pos]==0) stp[from][npos] = npos;
                else stp[from][npos] = stp[from][pos];
                pq.push({ ans[from][npos],npos });
            }
        }
    }
}
 
void input() {
    int to, from, dis;
    cin >> n >> m;
    while (m--) {
        cin >> to >> from >> dis;
        map[to].push_back({ from,dis });
        map[from].push_back({ to,dis });
    }
}
 
void output() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) cout << "-" << " ";
            else cout << stp[i][j] << " ";
        }
        cout << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    for (int i = 1; i <= n; i++) delivery(i);
    output();
    return 0;
}