반응형
https://www.acmicpc.net/problem/20924
20924번: 트리의 기둥과 가지
첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번
www.acmicpc.net
[ 문제풀이 ]
1. 그래프를 입력받고, list 배열에 저장합니다.
2. dfs를 이용하여 루트부터 탐색하면서 현재 노드까지의 길이를 저장하고, 그중 가장 긴 길이를 all에 저장합니다.
3. 자식 노드가 2개 이상인 노드의 길이 중 가장 짧은 길이를 gidung에 저장합니다.
4. gidung 과 all - gidung을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<vector> using namespace std; int N, R; int a, b, d; vector<pair<int, int>> list[200001]; int visited[200001]; int all; int gidung = 987654321; void dfs(int node, int dist) { int cnt = 0; all = max(all, dist); for (auto& next : list[node]) { if (visited[next.first] == 0) { cnt++; visited[next.first] = 1; dfs(next.first, dist + next.second); visited[next.first] = 0; } } if (cnt >= 2) { gidung = min(gidung, dist); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> R; for (int i = 0; i < N - 1; i++) { int a, b, d; cin >> a >> b >> d; list[a].push_back({ b,d }); list[b].push_back({ a,d }); } visited[R] = 1; dfs(R, 0); if (gidung == 987654321) { gidung = all; } cout << gidung << ' ' << all - gidung; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1351번 - 무한 수열 (C++) (0) | 2023.09.28 |
|---|---|
| [ 백준 ] 14925번 - 목장 건설하기 (C++) (0) | 2023.09.27 |
| [ 백준 ] 10835번 - 카드게임 (C++) (0) | 2023.09.25 |
| [ 백준 ] 3197번 - 백조의 호수 (C++) (0) | 2023.09.24 |
| [ 백준 ] 2015번 - 수들의 합 4 (C++) (0) | 2023.09.23 |
