📝 문제 정보 # 링크: 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$ 위와 같은 그래프가 있었다고 생각하자. 파란 간선 1개를 $1 - 2$ 같은걸 골라버리면 불가능해지는 문제가 생긴다. 잘 골라야 한다. 음.. 빨간색으로 미리 다 합쳐놓고, 나머지를 연결할 개수 이상의 파란간선은 필요한거 같은데.. 그런데, 이미 MST가 잘 있다면, 빨간 간선을 파란 간선으로 대체하는게 꽤 자유로운가? 이것만 되면 큰 문제가 없는데? $k > 1$ 주황색이 이미 만들어진 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는 기본적으로 연결되어있다고 판단하자.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1647 🧐 관찰 및 접근 # 집 (정점)과 길 (간선)이 있다. 마을 두개로 분리해야한다. 이 때, 간선의 가중치의 합을 최소화해야한다. 이미 두 집이 한 마을 안에 있다면, 둘이 연결할 필요가 없다. 이미 다른 우회로로 갈 수 있기 때문 연결하던 도중 마을이 두개가 남았다면 끝내면 된다. 크루스칼 알고리즘으로 덩어리가 두개가 남을때까지 반복하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<tuple<int, int, int>> edges; // weight, u, v rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; edges.emplace_back(w, u, v); } UF.init(N+1); sort(all(edges)); int ans = 0; for(auto &[w, u, v]: edges){ if(UF.group == 3) break; if(UF.merge(u, v)) ans += w; } cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10775 🧐 관찰 및 접근 # 1번 게이트가 제일 쓰기 좋아보인다. 그러므로 1번 게이트를 아낀다고 생각하면, 모든 비행기를 도킹시킬때 갈 수 있는 최댓값으로 도킹시키면 되는 것 같다. 이를 나이브하게 구현하면 한번당 $O(G)$가 걸릴 것이다. 100000 100000 100000 100000 100000 ... 과 같은 테스트케이스를 생각해보면 된다. 따라서 $\text{calc}(g_i) = g_i$ 보다 작거나 같은 살아있는 게이트의 최댓값을 빠르게 찾으면 된다. 이는 유니온파인드로 빠르게 수행 가능하다! merge할때 자신보다 작은 값을 가리키게 하자. 💻 풀이 # 코드 (C++): void solve(){ int G, P; cin >> G >> P; UF.init(G+1); int ans = 0; while(P--){ int g; cin >> g; int rt = UF.find(g); if(rt == 0) break; UF.merge(rt, rt-1); ans++; } cout << ans << "\n"; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1043 🧐 관찰 및 접근 # 지민이는 모든 파티에 참여해야하므로, 진실을 아는 사람이 있는 파티의 모든 사람은 진실을 알게 된다. 모든 파티에 대해 진실을 알게 된 사람을 확인한 후, 진실을 아는사람이 없는 파티들의 수를 세면 된다. 유니온 파인드, 분리 집합으로 해결하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> parties; UnionFind UF(N+1); // 0은 진실을 아는 사람 int cnt; cin >> cnt; rep(i, 0, cnt){ int a; cin >> a; UF.merge(0, a); } rep(i, 0, M){ cin >> cnt; vector<int> party(cnt); rep(j, 0, cnt) cin >> party[j]; parties.push_back(party); rep(j, 0, cnt-1) UF.merge(party[j], party[j+1]); } int ans = 0; for(auto party: parties){ bool flag = true; for(auto p: party) if(UF.find(p) == 0) flag = false; if(flag) ans++; } cout << ans; } 🔒 구현 코드 잠금