https://www.acmicpc.net/problem/1414
문제
> 다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다.
> 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다.
> 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.
> 다솜이의 집에는 N개의 방이 있다.
> 각각의 방에는 모두 한 개의 컴퓨터가 있다.
> 각각의 컴퓨터는 랜선으로 연결되어 있다.
> 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나,
또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.
> 다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.
> N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때,
다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.접근
주어진 랜선들의 길이를 수로 변환해 모두 더한다. 이게 가지고 있는 총 랜선의 길이다.
이제 N번까지의 컴퓨터를 이어야 하므로 주어진 행렬에 대해서 i와j가 같은 경우를 제외하곤 전부 양방향으로 가중치, 다음 컴퓨터로 관계를 저장한다.
우선순위 큐에서 이 관계 중 가중치가 가장 싼것만 뽑아오며 쓴 랜선길이를 누적하고 모두 연결되면 총 - 쓴길이 해서 출력하고 연결이안되면 -1을 출력한다.
최소스패닝트리의 prim알고리즘을 이용한다.
문제해결
> 컴퓨터의 연결관계를 저장할 connect벡터와, 가진 총 랜선의 길이 변수 sum, 연결된 컴퓨터를 나타낼 visited 벡터를 선언한다.
> N개의 컴퓨터에 대해 i와 j로 주어진 관계를 파악한며 tmp에 해당 i와 j를 연결하는데 쓰는 랜선의 길이를 저장한다.
> 문자0 이면 길이가 0, 'a'를 뺀값이 음수면 대문자이므로 'A'를 빼고 27을 더해 문제 조건에 맞게 만들어준다.
> 양수면 'a'를 빼고 1을 더해주며 전부 sum에 누적해 총 길이를 구한다.
> 이제 connect벡터에 관계를 저장하기 위해 i와 j가 같은 나 자신으로 가는 경로는 제하고,
연결을 못하는 길이 0도 제해주며 양방향으로 저장한다.
> 쓴길이를 저장할 rst변수와 가중치,도착점 쌍으로 다룰 우선순위 큐를 가중치 기준 오름차순으로 선언한다.
> 아무곳에서 시작해도 비용은 같으므로 가중치0으로 0번 컴퓨터 부터 큐에 넣고시작한다.
> MST를 구현한다. 큐의 맨앞, 즉 가장 싼 경로를 뽑아오고 이와 연결된 다음 경로를 큐에 넣는다.
> 뽑아 쓸때, 방문처리를 해주며 예외가 생기지 않게 해주며, 이미 연결된 컴퓨터를 또 연결하지 않게 한다.
> 연결이 끝나고 방문처리를 한번 돌며 false인 컴퓨터가 있으면 연결이 안됐다는 뜻이므로 -1을 출력한다.
> 없으면 총 랜선 sum에서 쓴 랜선rst를 빼서 출력한다.코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int sum = 0;
vector<vector<pair<int,int>>> connect;
vector<bool> visited;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
connect.resize(N);
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < N; j++)
{
int tmp = 0;
if (str[j] == '0') tmp = 0;
else if (str[j] - 'a' < 0) tmp = str[j] - 'A' + 27;
else tmp = str[j] - 'a' + 1;
sum += tmp;
if (i == j) continue;
if (tmp == 0) continue;
connect[i].push_back({ tmp, j });
connect[j].push_back({ tmp, i });
}
}
int rst = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
visited.assign(N, false);
pq.push({ 0, 0 });
while (!pq.empty())
{
int fc = pq.top().second;
int w = pq.top().first;
pq.pop();
if (visited[fc]) continue;
visited[fc] = true;
rst += w;
for (auto a : connect[fc]) pq.push({ a.first, a.second });
}
for (auto a : visited)
{
if (!a)
{
cout << -1 << '\n';
return 0;
}
}
cout << sum - rst << '\n';
}
후기
문자로 된 랜선의 길이를 처리하는게 까다로웠고, 문제가 조금 복잡하게 되어있었다. 하지만 MST를 다시한번 이해 할 수 있는 기회였다.
