[BOJ] 9370 : 미확인 도착지

문제 링크

9370번: 미확인 도착지 (acmicpc.net)

9370번: 미확인 도착지

어느 부분에서 틀렸는지 감이 안와서 한참을 헤맨 문제였다.

 

풀이

처음에 나는 다익스트라 알고리즘 한 번으로 풀려고 시도했다. 다익스트라로 돌면서 지정된 도로를 지나가기

전에는 도착점에 false를 표기하고 지정된 도로를 지나간 후 부터는 true를 표기하기로 했다.

그렇게 해서 만약 최단거리로 목적지를 갔을 때 true라고 표기돼있으면 그 목적지는 유효한 것으로 판단 하려고

했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
 
int T;
int n, m, t;
int s, g, h;
const int MAX_N = 2000 + 5;
const int INF = INT_MAX;
vector<pair<int, int>> Edge[MAX_N];
vector<int> goal;
vector<int> dist(MAX_N, INF);
bool is_passed[MAX_N];
 
void dijkstra(int st) {
    priority_queue<pair<pair<int, int>, bool>, vector<pair<pair<int, int>, bool>>, greater< pair<pair<int, int>,bool>>> pq;
    pq.push({{0,st}, false});
    while (!pq.empty()) {
        int now = pq.top().first.second;
        int cost = pq.top().first.first;
        bool is_pass = pq.top().second;
        pq.pop();
        if (dist[now] != INF) {
            if (dist[now] < cost)
                continue;
            else {
                is_passed[now] = is_pass;
            }
        }
        else {
            dist[now] = cost;
            is_passed[now] = is_pass;
        }
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            int acost = cost + Edge[now][i].second;
            bool next_passed;
            if (now == g && next == h)
                next_passed = true;
            else if (now == h && next == g)
                next_passed = true;
            else next_passed = is_pass;
            if (dist[next] != INF) {
                if (dist[next] < acost)
                    continue;
                if (is_passed[next])
                    continue;
            }
            pq.push({ { acost,next }, next_passed });
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> n >> m >> t; //정점, 노드, 목적지 개수
        cin >> s >> g >> h; //시작점, 정점1, 정점2
        int from, to, distance;
        for (int i = 0; i < m; i++) {
            cin >> from >> to >> distance;
            Edge[from].push_back({ to,distance });
            Edge[to].push_back({ from, distance });
        }
        for (int i = 0; i < t; i++) {
            cin >> to;
            goal.push_back(to);
        }
        fill(dist.begin(), dist.end(), INF);
        dijkstra(s);
        sort(goal.begin(), goal.end());
        for (int i = 0; i < goal.size(); i++) {
            if (dist[goal[i]] != INF && is_passed[goal[i]]) {
                cout << goal[i] << " ";
            }
        }
        cout << "\n";
        for (int i = 0; i <= n; i++) {
            Edge[i].clear();
        }
        goal.clear();
        memset(is_passed, false, sizeof(is_passed));
    }
    return 0;
}

언뜻 보면 맞는 코드라 계속 맞왜틀인줄 알았다. 그러다 질문검색에서 반례를 찾다가 깨달았다. 만약 지정된 도로를 지나서 목적지까지 도달하는 거리와 지나지 않고 목적지까지 도달한 거리가 같다면? 어떤 경우에는 true가 기록되고 어떤 경우에는 false가 기록될 수 있다. 이런 경우에는 false 위에 true를 덧칠하려 했지만 그렇게 되면 경우의 수가 너무 많아져서

메모리 초과가 났다.

결국 아이디어를 수정했다.

1. s를 출발점으로 다익스트라 알고리즘을 돌린 후 최단거리를 S[] 배열에 저장한다.

2. g를 출발점으로 G[] 배열에 저장

3. h를 출발점으로 H[] 배열에 저장

그 후 S->G->H->목적지 또는 S->H->G->목적지 이 두 코스의 거리와 최단경로인 S[목적지]가 같으면 그때는 유효한 목적지다 라고 판단.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
#define INF  987654321
#define MAX_N 2010
using namespace std;
 
int T;
int n, m, t;
int s, g, h;
vector<pair<int, int>> Edge[MAX_N];
vector<int> goal;
int S[MAX_N];
int H[MAX_N];
int G[MAX_N];
 
void dijkstra(int st, int Arr[MAX_N]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0,st });
    while (!pq.empty()) {
        int now = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if (Arr[now] != INF)
            continue;
        else Arr[now] = cost;
        for (int i = 0; i < Edge[now].size(); i++) {
            int next = Edge[now][i].first;
            int acost = cost + Edge[now][i].second;
            if (Arr[next] != INF)
                continue;
            else pq.push({ acost, next });
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        for (int i = 0; i < MAX_N; i++) {
            Edge[i].clear();
            S[i] = INF;
            G[i] = INF;
            H[i] = INF;
        }
        goal.clear();
 
        cin >> n >> m >> t; //정점, 노드, 목적지 개수
        cin >> s >> g >> h; //시작점, 정점1, 정점2
 
        int from, to, distance;
        for (int i = 0; i < m; i++) {
            cin >> from >> to >> distance;
            Edge[from].push_back({ to,distance });
            Edge[to].push_back({ from, distance });
        }
        for (int i = 0; i < t; i++) {
            int a;  cin >> a;
            goal.push_back(a);
        }
        dijkstra(s,S);
        dijkstra(g,G);
        dijkstra(h,H);
        sort(goal.begin(), goal.end());
        for (int i = 0; i < goal.size(); i++) {
            int Goal = goal[i];
            if (S[Goal] == S[g] + G[h] + H[Goal]) // S->G->H->Goal
                cout << Goal << " ";
            else if (S[Goal] == S[h] + H[g] + G[Goal]) // S->H->G->Goal
                cout << Goal << " ";
        }
        cout << "\n";
    }
    return 0;
}