Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/4792
4792번: 레드 블루 스패닝 트리
무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내
www.acmicpc.net
풀이
solved.ac 난이도: Platium 3
최소 스패닝 트리(MST)를 적용하여 해결하는 문제.
처음에는 어떤 부분이 MST 문제인지도 감을 못 잡아서 결국 다른 분의 풀이를 보고 해결했다.
4Legs_Archives님의 [백준]레드 블루 스패닝 트리 풀이
문제의 풀이는 난이도에 비해 간단하지만 증명을 어떻게 유도하는 것이 어려웠다.
일단 풀이는 다음과 같다.
1. 파란 간선의 최소로 사용하는 스패닝 트리를 구한다.
이때 파란 간선의 cost를 1, 빨간 간선의 cost를 0으로 저장하여 크루스칼 알고리즘은 진행하면
빨간 간선들의 가중치가 더 낮기 때문에 빨간 간선을 우선적으로 스패닝 시킨다.
따라서 최소 스패닝 트리의 가중치는 스패닝 트리에 포함된 파란 간선의 개수(min_blue)와 같다.
2. 파란 간선의 최대로 사용하는 스패닝 트리를 구한다.
이때는 파란 간선의 cost를 0,빨간 간선의 cost를 1로 저장하여 크루스 칼 알고리즘은 진행한다.
파란 간선이 우선적으로 스패닝 되므로 최소 스패닝 트리의 가중치는 빨간 간선의 개수이다.
따라서 파란 간선의 개수(max_blue)는 (정점의 개수 - 1) - 빨간 간선의 개수이다.
3. K값이 min_blue와 max_blue의 범위에 포함되는지 확인한다.
K가 범위 값에 포함되지 않는다면 파란 간선이 K개인 스패닝 트리를 만들지 못하는 것은 자명하다.
min_blue <= K <= max_blue이라면 파란 간선이 정확히 K개인 스패닝 트리를 만들 수 있다.
어째서일까?
다음의 그래프를 파란 간선을 최소로 사용한 스패닝 트리에서 최대로 사용한 스패닝 트리로 변경하는 과정을 생각해보자.
파란 간선을 최소로 사용한 스패닝 트리: min_blue = 1
파란 간선을 최대로 사용한 스패닝 트리: max_blue = 4
파란 간선을 최소로 사용한 스패닝 트리에 다른 파란 간선 1개를 추가 시켜 사이클을 만들어 준다 하자.
이제 1, 2, 3 정점들 간의 사이클이 생겼으므로 해당 사이클에서 빨간 간선을 하나 제거해주자.
이러면 여전히 모든 정점이 연결된 트리 상태를 유지하면서 파란 간선의 개수는 한 개 증가하였다.
동일한 작업을 반복해주면 결국 파란 간선을 최대로 사용한 스패닝 트리의 형태로 변경되게 된다.
따라서 K값이 min_blue이상이고 max_blue 이하라면 K개의 파란 간선을 가지는 스패닝 트리를 만들 수 있다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.1420 - 학교 가지마! (C++, 최소 컷, 최대 유량, 정점 분할) (0) | 2021.06.02 |
|---|---|
| [백준] No.6086 - 최대 유량 (C++, 최대 유량) (0) | 2021.05.30 |
| [백준] No.1185 - 유럽여행 (C++, MST 크루스칼) (0) | 2021.05.24 |
| [백준] No.2887 - 행성 터널 (C++, 크루스칼 MST) (0) | 2021.05.23 |
| [백준] No.1944 - 복제 로봇 (C++, 크루스칼 MST) (0) | 2021.05.22 |