boj 2132 나무 위의 벌레

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

 

4년 전에 풀지 못한 문제를 지금에서야 풀게되었습니다.

그땐 어려웠지만 지금도 어렵네요 ㅎ

 

이 문제는 어디서든 출발이 가능하며, 열매를 최대한 많이 먹을 수 있는 경로를 찾아야 합니다.

문제 자체는 트리의 지름 문제와 같은 문제입니다.

열매가 트리의 가중치라고 생각하고 접근한다면 쉽게 해결할 수 있습니다.

 

문제의 로직은

1. 처음 출발할 정점으로 아무지점이나 정합니다. (풀이에서는 1번 정점에서 출발)

2. 1에서 정한 출발 정점에서 가장 열매를 많이 먹을 수 있는 위치를 찾습니다.

3. 2에서 구한 최대 갯수가 정답이 되며, 해당 경로의 양쪽 끝은 1, 2에서 구한 정점이 됩니다. 따라서 두 정점 중 번호가 낮은 정점을 출력합니다.

 

저는 bfs로 풀었지만 dfs로도 풀리는 것으로 알고있어서 시간이 된다면 풀어봐야되겠네요.

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10001
using namespace std;
typedef pair<int, int> pii;
 
vector<int> v[MAX];
int list[MAX];
int w[MAX];
int weight, idx;
int N;
 
bool isHigher(int we, int i, int x) {
    if (we == w[x]) {
        return i > x;
    }
    return we < w[x];
}
 
void bfs(int x) {
    memset(w, -1, sizeof(w));
 
    queue<int> q;
    q.push(x);
    w[x] = list[x];
    weight = list[x];
    idx = x;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        if (isHigher(weight, idx, now)) {
            idx = now;
            weight = w[now];
        }
 
        for (auto next : v[now]) {
            if (w[next] != -1) continue;
            w[next] = w[now] + list[next];
            q.push(next);
        }
    }
}
 
void func() {
    bfs(1);
    int tmp = idx;
    bfs(idx);
    cout << weight << ' ' << min(tmp, idx) << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
 
    int x, y;
    for (int i = 1; i < N; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}