[BOJ 10273 // C++] 고대 동굴 탐사

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10273번 문제인 고대 동굴 탐사이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10273

10273번: 고대 동굴 탐사

이 문제는 주관적으로 영어로 읽는 편이 문제 이해에 도움이 되었다.

 

이 문제는 위상정렬(topological sorting)로 해결하기 좋은 문제이다.

글쓴이는 BFS를 진행하면서 탐색하고자 하는 노드의 먼저 조사해봐야 할 진입로의 개수를 하나씩 깎다가 0개가 되면 그 때 BFS의 대상에 집어넣는 방식으로 위상정렬을 구현했다.

이 과정에서, 해당 노드까지 탐사했을 때 얻을 수 있는 최대의 이익과, 그 노드로 진입하는 노드를 기록해나간다.

또한, 그 이익이 기존의 최대 이익보다 크다면, 해당 노드를 현재까지의 최대이익이 나오는 노드로 기록해둔다.

 

동굴을 탐사하면 할수록 손해만 보는 경우가 있을 수 있음에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin; using std::cout;
using std::vector;
using std::pair;
using std::queue;

void solve() {
    int N, E; cin >> N >> E;
    vector<pair<int, int>> G[20001];
    int gemstone[20001];
    int earn[20001];
    int needcheck[20001];
    int parent[20001];

    for (int i = 1;i <= N;i++) {
        int temp; cin >> temp;
        gemstone[i] = temp;
        earn[i] = -999999999;
        needcheck[i] = 0;
    }
    for(int i = 0;i < E;i++) {
        int x, y, z; cin >> x >> y >> z;
        G[x].push_back({ y,z });
        needcheck[y]++;
    }
    int ans = 1;
    earn[ans] = gemstone[ans];
    queue<int> que; que.push(1);
    while (!que.empty()) {
        int current = que.front(); que.pop();
        if (earn[current] > earn[ans]) ans = current;
        vector<pair<int,int>>::iterator iter = G[current].begin();
        while (iter != G[current].end()) {
            needcheck[(*iter).first]--;
            if (earn[(*iter).first] < earn[current] - (*iter).second + gemstone[(*iter).first]) {
                earn[(*iter).first] = earn[current] - (*iter).second + gemstone[(*iter).first];
                parent[(*iter).first] = current;
            }
            if (needcheck[(*iter).first] == 0) que.push((*iter).first);
            iter++;
        }
    }
    cout << earn[ans] << ' ';
    vector<int> stk;
    while (ans != 1) {
        stk.push_back(ans);
        ans = parent[ans];
    }
    stk.push_back(1);
    cout << stk.size() << '\n';
    while (!stk.empty()) {
        cout << stk.back() << ' '; stk.pop_back();
    }
    cout << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for (int i = 0;i < T;i++) {
        solve();
    }
    return 0;
}