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<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;
}
|
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 |