[BOJ 백준] 9370번 미확인 도착지

문제

BOJ 9370 : https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

접근

이 문제는 출발지(s)에서 목적지 후보까지 가는 최단 거리 루트에서 g-h의 길을 지나는 목적지들을 찾는 문제이다. 이는 다익스트라 알고리즘(Dijkstra algorithm)을 응용하여 풀 수 있다.

우선순위 큐를 이용하여 출발지(s)부터 각 지점까지의 최단 거리를 갱신하며 전진한다. 이때 각 지점까지의 최단 루트가 g-h길을 포함하는지 체크해 나가면서 진행한다.

큰 응용을 요구하는 건 아니지만 푸는 과정에서 몇몇 예외를 간과하는 실수를 하였다. 나는 진행하다가 목적지 후보에 도착하면 continue를 해줬었는데, 다른 목적지 후보 중에 현재 목적지까지의 루트 + α의 루트를 최단 경로로 가질 수 있음으로 continue 해주면 안 된다.

 

+) 본인은 코드를 짤 때 예를 들면 int next = v[x[i].first] 이런 식으로 가독성 좋게 짜는 편이 아니다..(몇 번을 쓰더라도 변수를 따로 만들지 않고 v[x[i].first]을 그대로 호출한다.) 직관적으로 구조가 보이게 짜기 때문에 코드가 너무 복잡하다고 느껴진다면 vscode로 가지고 가서 직접 치환해보시길 바란다. 코드를 이해하는 데 도움이 될 것이다.

 

코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct go {
    int point;
    int n = 0;
    int chk = 0;
};

struct cmp {
    bool operator()(go a, go b) {
        if (a.n == b.n)
            return a.chk >= b.chk;
        return a.n < b.n;
    }
};

int main() {
    int testcase;
    cin >> testcase;
    for (int t = 0; t < testcase; t++) {
    	// input
        int n, m, tt, s, g, h, goal[2010] = {0};
        cin >> n >> m >> tt >> s >> g >> h;
        vector<pair<int, int>> map[2010];
        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            map[a].push_back(make_pair(b, d));
            map[b].push_back(make_pair(a, d));
        }
        for (int i = 0; i < tt; i++) {
            int temp;
            cin >> temp;
            goal[temp] = 1;
        }
        
        // Dijkstra algorithm
        priority_queue<go, vector<go>, cmp> q;
        q.push({s, 0, 0});
        int visit[2010] = {0};
        int chk_v[2010] = {0};
        while (!q.empty()) {
            go temp = q.top();
            q.pop();

            if (goal[temp.point] == 1 && temp.chk == 1)
                goal[temp.point] = -1;
            if (temp.chk == 1)
                chk_v[temp.point] = 1;
            int chk = 0;
            for (int i = 0; i < map[temp.point].size(); i++) {
                chk = 0;
                if ((temp.point == g && map[temp.point][i].first == h) || (temp.point == h && map[temp.point][i].first == g) || temp.chk == 1)
                    chk = 1;
                if ((visit[map[temp.point][i].first] == temp.n + map[temp.point][i].second && chk == 1) && chk_v[map[temp.point][i].first] != 1)
                    q.push({map[temp.point][i].first, temp.n + map[temp.point][i].second, chk});
                else if (visit[map[temp.point][i].first] == 0 || visit[map[temp.point][i].first] > temp.n + map[temp.point][i].second) {
                    if (goal[map[temp.point][i].first] == -1)
                        goal[map[temp.point][i].first] = 1;
                    visit[map[temp.point][i].first] = temp.n + map[temp.point][i].second;
                    if (chk == 0)
                        chk_v[map[temp.point][i].first] = 0;
                    else
                        chk_v[map[temp.point][i].first] = 1;
                    q.push({map[temp.point][i].first, temp.n + map[temp.point][i].second, chk});
                }
            }
        }
        for (int i = 0; i < 2001; i++) {
            if (goal[i] == -1)
                cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study