불우이웃돕기 (feat. 백준, 1414번)

불우이웃돕기
https://www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int visit[51]{false};
int arr[51][51];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, total = 0, ans = -1;
    cin >> N;
    string str;
    for(register int i = 1, j, v; i <= N; ++i){
        cin >> str;
        for(j = 1; j <= N; ++j){
            if(str.at(j - 1) == '0')
                v = 999999999;
            else if('a' <= str.at(j - 1) && str.at(j - 1) <= 'z')
                v = static_cast<int>(str.at(j - 1) - 'a') + 1;
            else if('A' <= str.at(j - 1) && str.at(j - 1) <= 'Z')
                v = static_cast<int>(str.at(j - 1) - 'A') + 27;
            arr[i][j] = v;
            if(v != 999999999)
                total += v;
        }
    }
    for(register int n = 1, t, c; n <= N; ++n){
        c = 0;
        memset(visit, false, N + 1);
        t = total;
        q.push(make_pair(0, n));
        while(!q.empty()){
            auto next = q.top().second, cost = q.top().first; q.pop();
            if(visit[next])
                continue;
            visit[next] = true;
            t -= cost, ++c;
            for(auto nn = 1; nn <= N; ++nn){
                if(arr[nn][next] == 999999999 && arr[next][nn] == 999999999)
                    continue;
                q.push(make_pair(min(arr[nn][next], arr[next][nn]), nn));
            }
        }
        if(c == N)
            ans = max(ans, t);
        else
            ans = max(ans, -1);
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 프림 알고리즘을 활용하였습니다.

기존의 MST와 조금 다른 점은 동일한 A11, A22 와 같은 위치에도 값이 있다는 것입니다.

또한 MST 시작점이 1 - N까지를 모두 검사해야 합니다.