📝 문제 정보 # 링크: 번역 문제 # Farmer John은 소들의 방목 패턴을 더 잘 관리하기 위해 농장 전체에 일방통행 소 길들을 설치했습니다. 농장은 N개의 목초지로 구성되어 있으며, 편의상 1부터 N까지 번호가 매겨져 있고, 각 일방통행 소 길은 한 쌍의 목초지를 연결합니다. 예를 들어, 목초지 X에서 목초지 Y로 연결되는 길이 있다면, 소들은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23569 번역 문제 번역 # 문제 설명 # 사람들 간의 상호작용이 주어질 때, 정점이 사람들이고 두 사람이 서로 친구인 경우에만 그들 사이에 간선이 있는 그래프를 정의할 수 있습니다. 이러한 그래프를 소셜 네트워크라고 하며, 예를 들어 대학의 학생들이나 작은 마을의 주민들과 같은 모든 사람들의 집합에 대해 잘 정의됩니다. 최근 몇 년간 소셜 네트워크를 분석하는 완전한 과학 분야가 생겨났는데, 이는 사람들과 그들의 행동에 대한 많은 흥미로운 측면들이 이 친구 관계 그래프의 속성으로 가장 잘 이해되기 때문입니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32144 🧐 관찰 및 접근 # 문제에 내 이름이 나와서 기분이 좋다. 서브트리를 하나 잡아서, 그 서브트리의 루트와 그 부모와의 연결을 끊고 서브트리의 임의의 정점과 방금 끊은 부모를 연결하는 연산을 할 수 있다. 직관적으로, 해당 서브트리에서 줄 수 있는 길이의 가중치가 깊이에서 지름으로 바뀜을 알 수 있다. Tree DP를 이용한 트리의 지름 구하기 방법을 이용하면 좋을 것 같다. ![[Drawing 2026-01-25 10.09.49.excalidraw.png]] 위와 같은 경우같은게 발생할 것 같다. 두번째로 작은 트리의 지름과 마찬가지로, 기존 지름의 양 끝 점중 한 점은 유지된다. …인줄알았는데 안된다. ![[Drawing 2026-01-25 11.07.01.excalidraw.png]] 다음과 같이 서브노드 안에 기존 트리의 지름이 다 있는 경우도 있다… 결국 문제에서도 말하는 것처럼 문제를 부분트리와 그 나머지로 보면, 리루팅이 가능하지 않을까? 리루팅을 이용해서, 다음과 같은 정보를 저장하자. 서브트리의 지름 해당 서브트리에서 가장 깊은 깊이 두개 (리루팅용) 해당 노드에서 위로 갔을때, 가장 깊은 길이 이는 dfs를 이용해서 구현 가능하고, 시간복잡도는 $O(N)$이다. 디버깅을 위한 예제 2번 그림 ![[Drawing 2026-01-25 10.30.52.excalidraw.png]] 💻 풀이 # 코드 (C++): int N; vector<int> links[300005]; vector<pii> max_depth[300005]; int diam[300005]; int updepth[300005], updiam[300005]; vector<pii> dfs(int cur, int par){ vector<pii> v; v.push_back({0, cur}); for(auto nxt: links[cur]){ if(nxt == par) continue; auto nv = dfs(nxt, cur); diam[cur] = max(diam[cur], diam[nxt]); v.push_back({nv[0].first + 1, nxt}); sort(all(v), greater<pii>()); while(v.size() > 2) v.pop_back(); } if(v.size() >= 2) diam[cur] = max(diam[cur], v[0].first + v[1].first); else diam[cur] = max(diam[cur], v[0].first); max_depth[cur] = v; // cout << "cur: " << cur << " diam: " << diam[cur] << " max_depth: "; // for(auto p: v) cout << "(" << p.first << "," << p.second << ") "; // cout << '\n'; return v; } void dfs2(int cur, int par){ for(auto nxt: links[cur]){ if(nxt == par) continue; updepth[nxt] = updepth[cur] + 1; if(max_depth[cur][0].second != nxt) updepth[nxt] = max(updepth[nxt], max_depth[cur][0].first + 1); else if(max_depth[cur].size() >= 2) updepth[nxt] = max(updepth[nxt], max_depth[cur][1].first + 1); dfs2(nxt, cur); } } void solve(){ cin >> N; rep(i, 2, N+1){ int p; cin >> p; links[p].push_back(i); links[i].push_back(p); } dfs(1, -1); dfs2(1, -1); rep(i, 2, N+1) cout << max(diam[1], updepth[i] + diam[i]) << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/19581 🧐 관찰 및 접근 # 가중치 없는 트리인줄 알고, 당연히 지름-1이 답이 아닌가? 했더니 가중치가 있었다 가중치가 있는 트리라면, 우리가 원래 쓰던 DFS두번이라는 방법은 쉽지 않을것같다 가장 긴 트리의 지름과, 두번째로 긴 트리의 지름이 아예 관계 없는 곳에 있을 수도 있지 않을까? 아닌가? ![[Drawing 2026-01-25 09.41.32.excalidraw.png]] 트리의 지름과 두번째 트리의 지름이 끝 정점을 공유하지 않는다고 하자. 그렇다면, 위 그림과 같이 압축해서 나타낼 수 있다. 이 때, $a + b = D_1 \geq c + d = D_2$라 하자. 일반성을 잃지 않고 $a \geq b, c \geq d$라 하자. 서로 공유하는 정점 하나가 있는 경우 $a + c \geq D_1/2 + D_2/2 \geq D_2$ 이므로, a와 c를 지나는 경로가 우리가 가정한 두번째 지름보다 더 크거나 같다. 더 큰 경우 모순이고 같은 경우 $a+c$를 두번째 지름으로 택해도 아무 문제가 없다. 서로 공유하는 정점이 없는경우 (다른 서브트리에 나타낼 수 있는 경우) $a + c + e + f \geq D_1/2 + D_2/2 + e + f > D_2$ 이므로, $D_2$의 경로는 두번째 트리의 지름이 아니다. 따라서, 트리의 두번째 지름의 한 끝점은 트리의 지름의 한 끝점과 같다. DFS를 돌려서 트리의 지름 양 끝 점을 찾고, 거기서부터 두번째지름을 한번씩 찾아주자. 💻 풀이 # 코드 (C++): vector<pii> dfs(int cur, int par){ vector<pii> v; v.push_back({0, cur}); for(auto [nxt, w]: links[cur]){ if(nxt == par) continue; auto nv = dfs(nxt, cur); rep(i, 0, min(2, (int)nv.size())){ v.push_back({nv[i].first + w, nv[i].second}); } sort(all(v), greater<pii>()); while(v.size() > 2) v.pop_back(); } return v; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int L = dfs(1, -1)[0].second; // 트리의 지름의 한쪽 끝 int ans = 0; auto ret = dfs(L, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 1 int R = ret[0].second; // 트리의 지름의 다른쪽 끝 ret = dfs(R, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 2 cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5639 🧐 관찰 및 접근 # 이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자! 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데… 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다. 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로 50 (루트) --- 30 (왼쪽 서브트리) 24 5 28 45 --- 98 (오른쪽 서브트리) 52 60 첫 입력에 대해, 이렇게 생각할 수 있지 않을까? 그리고 각 서브트리 또한 이진 검색트리이므로, 이를 재귀적으로 수행할 수 있다. 예를 들어, 왼쪽 서브트리에 대해서 30 (루트) --- 24 (왼쪽 서브트리) 5 28 --- 45 (오른쪽 서브트리) 위와 같이 말이다! 그렇다면, 재귀를 이용해서 트리를 구축하고 후위순회만 하면 끝난다. 💻 풀이 # 코드 (C++): vector<int> v; struct Node{ int val = -1; Node* left = nullptr; Node* right = nullptr; Node(int s, int e){ val = v[s]; if(s == e) return; int idx = e+1; rep(i, s+1, e+1){ if(v[i] > val){ idx = i; break; } } if(s+1 <= idx-1) left = new Node(s+1, idx-1); if(idx <= e) right = new Node(idx, e); } }; void postorder(Node* node){ if(node == nullptr) return; postorder(node->left); postorder(node->right); cout << node->val << '\n'; } void solve(){ int x; while(cin >> x) v.push_back(x); Node* root = new Node(0, v.size()-1); postorder(root); } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5214 🧐 관찰 및 접근 # 나이브하게 생각해볼까? 인접 리스트로 간선을 저장한다고 생각하면, $M\binom{K}{2} \approx MK^2$ 개의 정보가 저장된다. 그러면 BFS의 시간복잡도는 $O(V+E)$ 니까 조금 곤란한데… 잘 생각해보면, (1, 2, 3, 4), (2, 3, 4, 5) 하이퍼튜브가 있다고 가정하면, 겹치는 정보가 너무나도 많다! 첫 하이퍼튜브를 타고 2, 3, 4번 역에 1회만에 도착했다면, 두번째 하이퍼튜브에서 2, 3, 4번이 서로를 움직일 필요가 없다. 하이퍼튜브는 최대 1000개 존재한다. 또한 한 역은 최대 1000개의 하이퍼튜브에 속한다. 하이퍼튜브만 따로 정리해서, 그 안에서 움직이면 되지 않을까? 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> K >> M; rep(i, 0, M){ rep(j, 0, K){ int x; cin >> x; inhyper[x].push_back(i); hypertube[i].push_back(x); } } rep(i, 1, N+1) dist[i] = -1; dist[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int cur = q.front(); q.pop(); if(cur == N) break; for(int htube : inhyper[cur]){ for(int nxt : hypertube[htube]){ if(dist[nxt] == -1){ dist[nxt] = dist[cur] + 1; q.push(nxt); } } hypertube[htube].clear(); // 이미 방문한 하이퍼튜브는 볼일이 없다 } } cout << dist[N] << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2263 🧐 관찰 및 접근 # 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하자. 인오더: (왼쪽 -> 루트 -> 오른쪽) 포스트오더: (왼쪽 -> 오른쪽 -> 루트) 프리오더: (루트 -> 왼쪽 -> 오른쪽) 그렇다면, 어떤 한 서브트리에 대해, 포스트오더를 이용해서 루트를 찾을 수 있다. (맨 마지막 값) 그리고 이를 기점으로 인오더에서 왼쪽에 있는 모든 수는 왼쪽 서브트리, 나머지는 오른쪽 서브트리에 있다고 생각할 수 있다. 한 서브트리에서 루트노드의 값을 알아냈을 때, 인오더에서의 그 인덱스를 빠르게 찾을 수 있다면 왼쪽/오른쪽 서브트리로의 분할이 용이하다! map을 이용하면 $O(NlogN)$에 해결할 수 있겠다. 💻 풀이 # 코드 (C++): int N; vector<int> inorder, postorder; map<int, int> in_idx; void preorder(int in_s, int in_e, int post_s, int post_e){ if(in_s > in_e) return; int root = postorder[post_e]; cout << root << ' '; int idx = in_idx[root]; int sz = idx - in_s; preorder(in_s, idx-1, post_s, post_s + sz - 1); // 왼쪽 서브트리 preorder(idx+1, in_e, post_s + sz, post_e - 1); // 오른쪽 서브트리 } void solve(){ cin >> N; inorder.resize(N); postorder.resize(N); rep(i, 0, N) cin >> inorder[i]; rep(i, 0, N) cin >> postorder[i]; rep(i, 0, N) in_idx[inorder[i]] = i; preorder(0, N-1, 0, N-1); } 🔒 구현 코드 잠금