불우이웃돕기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

4904

2324

1839

47.178%

문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 부모 노드를 저장하는 벡터
static vector<int> Parents;

// 간선(Edge)을 나타내는 구조체
// 간선 구조체는 시작점, 끝점, 가중치를 가지며, 우선순위 큐에서 가중치를 기준으로 정렬될 수 있도록 operator >를 정의합니다.
typedef struct Edge {
    int s, e, v;  // 시작점, 끝점, 가중치
    bool operator > (const Edge& temp) const
    {
        return v > temp.v;  // 가중치 기준으로 우선순위 큐에서 정렬
    }
} Edge;

// 부모 노드를 찾는 함수 (경로 압축)
int Find(int a)
{
    if (Parents[a] == a)  // 부모가 자기 자신이면 그 자체가 루트 노드
    {
        return a;
    }

    // 부모를 재귀적으로 찾아가면서 경로 압축
    return Parents[a] = Find(Parents[a]);
}

// 두 집합을 합치는 함수 (합집합)
void Union(int a, int b)
{
    a = Find(a);  // a의 루트 노드 찾기
    b = Find(b);  // b의 루트 노드 찾기

    if (a != b)  // a와 b가 서로 다르면 합침
    {
        Parents[b] = a;  // b의 부모를 a로 설정
    }
}

int main()
{
    ios::sync_with_stdio(false);  
    cin.tie(NULL);
    cout.tie(NULL);

    int N, sum = 0;
    cin >> N;  // N은 노드의 개수 (즉, 간선의 수는 N-1개)

    // 우선순위 큐 선언 (간선의 가중치를 기준으로 오름차순으로 정렬)
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

    // 간선 정보를 입력받고 우선순위 큐에 넣기
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            // 문자 하나를 읽어오는 코드
            char tempc = cin.get();

            // 새로운 줄을 만났을 때, 불필요한 줄바꿈 문자를 처리
            if (tempc == '\n')
            {
                tempc = cin.get();
            }

            int temp = 0;

            // 문자에 따라 가중치를 계산
            if (tempc >= 'a' && tempc <= 'z')
            {
                temp = tempc - 'a' + 1;  // 'a'는 1, 'b'는 2, ..., 'z'는 26
            }
            else if (tempc >= 'A' && tempc <= 'Z')
            {
                temp = tempc - 'A' + 27;  // 'A'는 27, 'B'는 28, ..., 'Z'는 52
            }
            sum += temp;  // 가중치를 합산

            // i와 j가 같지 않고, 가중치가 0이 아닌 경우에만 간선 추가
            if (i != j && temp != 0)
            {
                pq.push(Edge{ i,j,temp });  // 우선순위 큐에 간선 삽입
            }
        }
    }

    // 부모를 자기 자신으로 초기화 (초기에는 모두 독립적인 집합)
    Parents.resize(N);
    for (int i = 0; i < N; i++)
    {
        Parents[i] = i;
    }

    int useEdge = 0;  // 사용된 간선의 개수
    int result = 0;   // 최소 스패닝 트리의 가중치 합

    // 우선순위 큐에서 간선을 하나씩 꺼내면서 최소 스패닝 트리를 구성
    while (!pq.empty())
    {
        Edge now = pq.top();  // 큐에서 가장 가중치가 작은 간선 꺼내기
        pq.pop();

        // 시작점과 끝점이 서로 다른 집합에 있을 경우 (사이클을 만들지 않음)
        if (Find(now.s) != Find(now.e))
        {
            Union(now.s, now.e);  // 두 집합을 합침
            result += now.v;      // 가중치를 결과에 더함
            useEdge++;            // 사용된 간선의 개수 증가
        }
    }

    // 최소 스패닝 트리가 가능한지 확인
    // 사용된 간선의 수가 N-1개라면 MST가 형성되었으므로 결과 출력
    if (useEdge == N - 1)
    {
        cout << sum - result;  // 전체 가중치에서 MST 가중치를 빼서 출력
    }
    else
    {
        cout << "-1";  // MST가 불가능하면 -1 출력
    }
}