백준 #14942 개미

BOJ #14942 - 개미

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

# 문제 분류

그래프 순회, 희소 테이블

풀이 접근 방법

  1. 2n2^n번 오른 뒤의 굴과 굴 간의 거리를 희소 테이블을 이용해 동일하게 표현할 수 있음은 자명하다.
  2. 그러나 중요한 사실은 트리의 루트가 없기 때문에, 만약 0으로 가는 경우가 있다면 막아주어야 한다.
  3. 2k2^k번 점프한다고 생각하면서, kk를 줄여가며 가능한 경우 에너지를 빼주면 가장 근접한 굴을 찾게 된다.
  4. 그러나 주어지는 입력이 트리의 순서라는 가정이 없기 때문에, DFS나 BFS를 이용해 트리의 순서를 찾아 주어야 한다.

희소 테이블 응용 + 트리 순회까지 사용해야하는 적절한 문제!

소스 코드

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

using namespace std;

int n, a, b, c;
const int MAX = 1e5 + 10;
const int MAX_D = 17;

int visit[MAX];
int ant[MAX][MAX_D];
int dist[MAX][MAX_D];
int energy[MAX];
vector<pair<int, int>> adj[MAX];
queue<int> s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> energy[i];
    }

    for (int i = 1; i < n; i++) {
        cin >> a >> b >> c;

        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }

    s.push(1);
    visit[1] = 1;
    while (!s.empty()) {
        int front = s.front();
        s.pop();

        for (auto &p : adj[front]) {
            int next = p.first;
            int d = p.second;

            if (visit[next])
                continue;

            visit[next] = 1;
            ant[next][0] = front;
            dist[next][0] = d;

            s.push(next);
        }
    }

    for (int j = 1; j < MAX_D; j++) {
        for (int i = 1; i <= n; i++) {
            ant[i][j] = ant[ant[i][j - 1]][j - 1];
            dist[i][j] = dist[i][j - 1] + dist[ant[i][j - 1]][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        int tmp = energy[i];
        int curr = i;
        for (int j = MAX_D - 1; j >= 0; j--) {
            if (tmp <= 0)
                break;
            if (tmp >= dist[curr][j] && ant[curr][j] != 0) {
                tmp -= dist[curr][j];
                curr = ant[curr][j];
            }
        }

        cout << curr << "\n";
    }
}