https://www.acmicpc.net/problem/1647
문제
> 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다.
> 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
> 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.
> 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.
> 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
> 임의의 두 집 사이에 경로가 항상 존재한다.
> 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.
> 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.
> 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
> 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다.
> 마을에는 집이 하나 이상 있어야 한다.
> 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다.
> 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.
> 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.
> 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.
> 이것을 구하는 프로그램을 작성하시오.접근
prim을 사용해서 최소스패닝트리를 구현해 푼다.
일단 마을을 최소의 비용으로 전부 이어준다. 그러면 불필요한 도로 싹다 사라지고 딱 필요한 최소비용으로 이루어진 도로만 남는다.
그렇게 도로를 이어주면서 젤 비싼 도로가 뭔지를 미리 잡아놓는다.
이제 그 도로를 없애주면 마을이 두 개로 쪼개진다.
그럼 가장 싼 두 마을을 만들 수 있다.
흐름을 정리하면 처음에 0비용으로 1번집에서 시작한다.
쌍은 (비용, 집번호)로 구성된다.
그럼 1번집과의 연결된 도로 중 비용이 싼 순으로 큐안에
(2,3) (2,6) (3,2) (5,5)이 들어온다.
순서대로 (2,3)이 뽑아져나오고 Max는 2, 비용은 2가된다.
3번집은 아직 방문 안했으므로 while문이 돌아가고 큐에
(1,2) (2,1) (4,4) (6,7)이 들어간다. 그러면 현재 큐는
(1,2) (2,1) (2,6) (3,2) (4,4) (5,5) (6,7)이 들어있다. 근데 여기서 1은 이미 연결 됐으므로 (2,1)은 제거된다.
다음으로 (1,2)가 뽑혀오고 Max는 2, rst는 3이 된고 큐는
(1,3) (2,5) (3,1) 중 방문 안한 (2,5)만 들어간다.
그럼 큐에 있는 (3,2)도 제거되며 결과적으로 큐에는
(2,5) (2,6) (4,4) (5,5) (6,7)가 있다.
(2,5)를 뽑아오고 Max는 2 rst는 5가 된다.
(2,2) (3,6) (3,4) (5,1) 중 (3,6) (3,4)만 큐에 들어가
(2,6) (3,6) (3,4) (4,4) (6,7)만 큐에 남는다.
(2,6)을 뽑고 Max는 2 rst는 7이 되며 큐에는
(1,4) (2,1) (3,5) (4,7)중 (1,4) (4,7)만 들어가서
(1,4) (3,4) (4,4) (4,7) (6,7)만 남는다.
(1,4)를 뽑으면 Max는 2, rst는 8이 되고 큐에
(1,6) (3,5) (4,3)중 들어갈 수 있는게 없다.
그럼 이제 큐에는 (4,7) (6,7)만 남고 더 싼 (4,7)이 뽑히고 Max는 4, 비용은 12가 된다.
모든 집이 연결됬으므로 큐에는 들어가는게 없고 들어있던 (6,7)도 제거된다.
그럼 이제 마을을 이등분 하기위해 젤 비싼 7번 집을 연결하는 도로를 없애고 비용도 12-4로 8이 되며 최종 두 마을이 남는다.
그래서 비용 8로 (1,2,3,4,5,6)마을 하나, (7)마을 하나 이렇게 남는다.
문제해결
> 집(노드)마다 연결했다고 표시할 방문처리용 부울 벡터와
집과 집사이 도로의 비용을 저장할 road벡터를 선언한다.
> 연결이 끝났을 때 가장 비싼 도로의 비용을 저장할 Max변수를 선언한다.
> 집을 연결하기위한 MST인 House 메소드를 정의해준다. 입력으로 최초의 비용, 최초 시작집이 들어온다.
> 우선순위 큐를 쌍을 입력받게 만들어주고 인자로 들어온 비용과 시작집을 큐에 넣고 시작한다.
> while문 자체는 이미 연결된 집에 대해선 실질 처리 부분이 아무것도 호출되지 않는다.
> 따라서 Max를 갱신하는 부분과 rst에 비용을 누적하는 부분도 연결이 이루어질 때만 호출된다.
> 최종 rst에서 Max에 저장했던 젤 비싼 도로를 빼준다.
이게 마을을 이등분 하는 부분이다. 그리고 비용을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M;
vector<bool> visited;
vector<vector<pair<int, int>>> road;
int Max = 0;
void House(int weight, int start)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ weight, start });
int rst = 0;
while (!pq.empty())
{
int tw = pq.top().first;
int tnode = pq.top().second;
pq.pop();
if (visited[tnode]) continue;
visited[tnode] = true;
Max = max(Max, tw);
rst += tw;
for (auto a : road[tnode]) pq.push({ a.first, a.second });
}
cout << rst - Max << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
visited.assign(N + 1, false);
road.resize(N+1, vector<pair<int, int>>());
while (M--)
{
int s;
int e;
int w;
cin >> s >> e >> w;
road[s].push_back({ w, e });
road[e].push_back({ w, s });
}
House(0, 1);
}
후기
아직 prim이 익숙치 않아 계속 따라가고 따라가고 하느라 헷갈리고 오래걸렸지만 제대로 따라갔다.
집을 이등분하는 방법을 다 연결하고 젤 비싼 도로를 잘라버리면 되는건 정말 획기적이다.
