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

 

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

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

 

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

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

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

 

문제의 로직은

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

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

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

 

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10001
using namespace std;
typedef pair<intint> 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, -1sizeof(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] != -1continue;
            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;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 2412 암벽 등반  (0) 2024.06.22
boj 14497 주난의 난(難)  (0) 2024.06.21
boj 16985 Maaaaaaaaaze  (0) 2022.12.16
boj 14466 소가 길을 건너간 이유 6  (0) 2022.10.13
boj 18112 이진수 게임  (0) 2022.09.16

+ Recent posts