📝 문제 정보 # 링크: https://www.acmicpc.net/problem/9938 🧐 관찰 및 접근 # 더 자세히 생각해보면, $(1, 2), (3, 4), (2, 3)$의 술병이 있는 경우, $1, 2, 3, 4$ 4개의 서랍중 3개의 서랍에 술이 들어갈 수 있다는 것을 알 수 있다. $A_i, B_i$를 보면서 분리 집합으로 묶어버린 뒤, 그 집합의 크기에 여유가 있다면 술병을 정리할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ int N, L; cin >> N >> L; UnionFind UF(L); rep(i, 0, N){ int a, b; cin >> a >> b; a--; b--; UF.merge(a, b); if(UF.val[UF.find(a)] < UF.cnt[UF.find(a)]){ cout << "LADICA\n"; UF.add(a, 1); } else{ cout << "SMECE\n"; } } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3830 🧐 관찰 및 접근 # 두 값의 차이를 트리 형태로 저장한다고 생각하자. 간선에 가중치가 있는 트리가 될 것이다. 두 값 $a, b$가 같은 트리에 있다면 비교 가능하고, 그렇지 않다면 비교 불가능하다. 하지만 이 경우 트리가 직선형이 되면, 최악의 경우 $O(N)$이 걸린다. 우리는 이러한 경우에 UnionFind에서 경로 압축을 하는 방법을 배웠다. 결국 루트까지의 간선 가중치 합을 저장해서 이용하면 된다. 💻 풀이 # 코드 (C++): void solve(){ while(1){ int N, M; cin >> N >> M; if(N + M == 0) break; UnionFind uf(N); while(M--){ char op; cin >> op; if(op == '!'){ int a, b, w; cin >> a >> b >> w; uf.merge(a-1, b-1, w); } else{ int a, b; cin >> a >> b; auto [ra, wa] = uf.find(a-1); auto [rb, wb] = uf.find(b-1); if(ra != rb) cout << "UNKNOWN\n"; else cout << wb - wa << '\n'; } } } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21932 번역 문제 번역 # 문제 설명 # 무방향 그래프가 주어지고, 각 노드에는 양의 정수 값이 연결되어 있습니다. 임계값(threshold)이 주어지면, 그래프의 노드들은 두 그룹으로 나뉩니다: 하나는 임계값 이하의 값을 가진 노드들로 구성되고, 다른 하나는 나머지 노드들로 구성됩니다. 이제 서로 다른 그룹에 속한 두 노드를 연결하는 모든 간선을 제거하여 얻은 원래 그래프의 부분 그래프를 고려합니다. 두 노드 그룹이 모두 비어있지 않을 때, 주어진 그래프가 연결되어 있는지 여부와 관계없이 결과 부분 그래프는 연결이 끊어집니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18180 번역 문제 번역 # 바이킹 락 운동에는 다양한 흐름이 존재한다. 올드 아이슬란드 그래니트 락, 미들 데니쉬 더스티 바이킹 락, 레이트 핀게일 다크 그린 락, 피오르드 볼더 아발란체 락 등, 인기 있는 흐름의 전체 목록을 나열하면 이 페이지를 여러 번 가득 채울 정도이다. 스칸디나비아 고등교육부는 이러한 흐름들이 서로 어떻게 영향을 주는지 연구하고 있다. 그들은 현재 대규모 실험을 계획 중이며, 적절히 선발된 자원봉사자들을 무인도들로 구성된 군도에 배치하여 상대적으로 긴 시간 동안 그들의 음악적 스타일과 선호도가 서로 미치는 영향을 관찰하고자 한다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2463 🧐 관찰 및 접근 # 간선에 가중치가 주어진 무향 그래프가 있다. 모든 간선의 가중치는 서로 다르다. $u$와 $v$사이의 최소 가중치 간선을 그래프에서 계속 제거해나가면서 $\text{Cost}(u, v)$를 구한다. $u, v$사이의 경로는 최대 가중치 간선만 남아있다. MST를 최댓값으로 하면 된다! 최댓값부터 MST를 진행하면서, 간선이 연결될때 양쪽 그룹의 크기의 곱만큼의 $\text{Cost}$ 관계를 계산하면서 구현할 수 있어보인다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<array<int, 3>> edges; mint sum = 0; rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; edges.push_back({w, u, v}); sum += w; } sort(all(edges), greater<array<int, 3>>()); UnionFind UF(N+1); mint ans = 0; for(auto [w, u, v]: edges){ if(UF.find(u) != UF.find(v)){ ans += sum * UF.cnt[UF.find(u)] * UF.cnt[UF.find(v)]; UF.merge(u, v); } sum -= w; } cout << ans << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4792 🧐 관찰 및 접근 # 파란색 간선을 $k$개, 빨간색 간선을 $(N-1) - k$개 이용해서 MST를 짜야하는데.. 일단 파란색 간선 $k$개를 결정하면 빨간색은 그냥 유파를 다해버리면 되니까, 파란색 간선을 잘 고르는게 중요하다. 나이브하게 한다면 $\binom{\binom{N}{2}}{k}$인가? 간선 개수는 그렇다 쳐도, $k$개를 고르는게 너무 큰디… 작은 문제부터 차근히 풀어보자. $k = 0$ 이라면 모든 간선들로 스패닝트리가 만들어지는지 확인하는 문제로 바뀐다. $k = 1$ ![[Drawing 2026-01-30 19.56.46.excalidraw.png]] 위와 같은 그래프가 있었다고 생각하자. 파란 간선 1개를 $1 - 2$ 같은걸 골라버리면 불가능해지는 문제가 생긴다. 잘 골라야 한다. 음.. 빨간색으로 미리 다 합쳐놓고, 나머지를 연결할 개수 이상의 파란간선은 필요한거 같은데.. 그런데, 이미 MST가 잘 있다면, 빨간 간선을 파란 간선으로 대체하는게 꽤 자유로운가? 이것만 되면 큰 문제가 없는데? $k > 1$ ![[Drawing 2026-01-30 20.04.04.excalidraw.png]] 주황색이 이미 만들어진 MST, 나머지를 남은 간선이라고 하자. 어떤 파란색 간선을 하나 쓰고싶으면, 두 정점으로 가는 경로에 있는 빨간색을 끊어버리고 파란색으로 새로 연결하면 된다! 이게 안되는 경우는 이미 그 두 정점으로 가는 경로가 다 파란색 간선만으로 연결된 경우인데.. 아하, 분리집합을 하나 더 관리하는걸로 쉽게 풀 수 있는 것 같다. 💻 풀이 # 코드 (C++): void solve(){ while(1){ int N, M, K; cin >> N >> M >> K; if(N + M + K == 0) break; vector<pii> Redges, Bedges; rep(i, 0, M){ char color; cin >> color; int u, v; cin >> u >> v; u--; v--; if(color == 'R') Redges.push_back({u, v}); else Bedges.push_back({u, v}); } UnionFind UF(N), BUF(N); // 일단 파란색 간선을 최소로 쓸때 되는지 확인 int cnt = 0; for(auto [u, v]: Redges) UF.merge(u, v); for(auto [u, v]: Bedges) if(UF.merge(u, v)){ cnt++; BUF.merge(u, v); } if(cnt > K){ cout << 0 << '\n'; continue; } // 빨간 간선을 하나하나 파란색으로 바꾸기 for(auto [u, v]: Bedges) if(BUF.merge(u, v)) cnt++; if(cnt < K){ cout << 0 << '\n'; continue; } cout << 1 << '\n'; } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2887 🧐 관찰 및 접근 # 누가봐도 MST를 짜야하는거같은데.. 행성 두개에 대해 모두 생각하면 간선의 개수가 $N^2$개가 된다… 그런데, 생각해보면 만약 행성 $A, B, C$가 있고, 세개 모두 $x$를 기준으로 연결했다고 하자. $x_A < x_B < x_C$라면, $x_A$와 $x_C$의 관계를 신경 쓸 필요가 있을까? 없다!! 따라서, $x, y, z$ 각각에 대해 정렬한 간선 $3N$개정도를 이용해서 MST를 짜자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<array<ll, 4>> planets; rep(i, 0, N){ int x, y, z; cin >> x >> y >> z; planets.push_back({x, y, z, i}); } vector<array<ll, 3>> edges; sort(all(planets), [](auto &a, auto &b){ return a[0] < b[0]; }); rep(i, 0, N-1) edges.push_back({abs(planets[i][0]-planets[i+1][0]), planets[i][3], planets[i+1][3]}); sort(all(planets), [](auto &a, auto &b){ return a[1] < b[1]; }); rep(i, 0, N-1) edges.push_back({abs(planets[i][1]-planets[i+1][1]), planets[i][3], planets[i+1][3]}); sort(all(planets), [](auto &a, auto &b){ return a[2] < b[2]; }); rep(i, 0, N-1) edges.push_back({abs(planets[i][2]-planets[i+1][2]), planets[i][3], planets[i+1][3]}); sort(all(edges)); UF.init(N); ll ans = 0; for(auto [w, u, v]: edges) if(UF.merge(u, v)) ans += w; cout << ans << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4195 🧐 관찰 및 접근 # 누가 봐도 유니온파인드 스타일이다. 문자열을 그대로 유니온 파인드에 넣긴 곤란하니, map 혹은 dict를 이용하자. 유니온 파인드를 구현할 때, 합을 잘 구해줘야한다. 분리 집합을 포레스트 모양이라고 생각할때, 각 트리의 루트노드에서 트리의 크기를 관리할 수 있도록 하면 쉽게 구현할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ int Q; cin >> Q; UF.init(Q*2); map<string, int> mp; while(Q--){ string A, B; cin >> A >> B; int a, b; if(mp.find(A) == mp.end()) mp[A] = mp.size(); if(mp.find(B) == mp.end()) mp[B] = mp.size(); a = mp[A]; b = mp[B]; UF.merge(a, b); cout << UF.cnt[UF.find(a)] << "\n"; } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1734 🧐 관찰 및 접근 # 무향 그래프 $G = (V, E)$가 주어진다.
여기서 두가지 쿼리가 주어진다.
간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 각각 살펴보자. 먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.