MST

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31055 번역 문제 번역 # Bessie는 수학 지식을 향상시키기 위해 그래프 이론 강좌를 수강하고 있는데, 다음 문제에서 막혔습니다. 그녀를 도와주세요! 연결된 무방향 그래프가 주어집니다. 정점은 $1\dots N$으로, 간선은 $1\dots M$으로 라벨링되어 있습니다 ($2\le N\le 2\cdot 10^5$, $N-1\le M\le 4\cdot 10^5$). 그래프의 각 정점 $v$에 대해 다음 과정을 수행합니다:

📝 문제 정보 # 링크: 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/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"; } 🔒 구현 코드 잠금