Moocast (feat. 백준, 14167번)

Moocast
https://www.acmicpc.net/problem/14167

14167번: Moocast

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
struct Cow{
    int x;
    int y;
};
Cow cows[1001];
vector<pair<int, int>> arr[1001];          // 다음 소 번호, 거리
bool visit[1001]{false};
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, next, nnext, dist, ans = 0;
    cin >> N;
    for(register int n = 1; n <= N; ++n)
        cin >> cows[n].x >> cows[n].y;
    for(register int i = 1, j; i < N; ++i)
        for(j = i + 1; j <= N; ++j)
            dist = pow(cows[i].x - cows[j].x, 2) + pow(cows[i].y - cows[j].y, 2), arr[i].push_back(make_pair(j, dist)), arr[j].push_back(make_pair(i, dist));
    q.push(make_pair(0, 1));
    while(!q.empty()){
        dist = q.top().first, next = q.top().second; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        if(dist > ans)
            ans = dist;
        for(auto& v : arr[next]){
            nnext = v.first, dist = v.second;
            if(!visit[nnext])
                q.push(make_pair(dist, nnext));
        }
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

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

저는 프림 알고리즘을 사용하여 풀이하였습니다.

첫 줄 N의 소의 마리수, 두번째 줄부터는 각 소의 좌표 (x,y) 입니다.

즉, 각각의 소를 연결지을때 가장 긴 거리를 구하는 문제입니다.

소와 소의 거리는 pow(x1-x2, 2) + pow(y1-y2, 2) 입니다.