백준 11085 - 군사 이동(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11085

11085번: 군사 이동

최소 스패닝 트리를 이용한 문제입니다.

C에서 V까지 가는데 비용이 최대가 되도록 만들어주는 것이 핵심입니다.

따라서 기존 최소 스패닝 트리와 달리, 정렬을 비용을 기준으로 내림차순으로 해주면 됩니다.

 

처음에는 X번째 connect 배열에 X값을 넣어줍니다.

해당 배열을 통해서 X가 어디에 연결되어 있는지를 저장합니다.

 

X와 Y가 서로 어디까지 연결되어 있는지를 각각 확인해야 합니다. 따라서 X와 Y를 Find() 함수를 통해서 연결된 끝지점을 확인해줍니다.

 

서로 연결된 지점이 같다면 두 점을 연결해줄 필요가 없습니다. 

따라서 다를 경우에만 연결해주면 됩니다. 이때 두 점을 Union() 함수를 통해서 연결해줍니다.

 

스패닝 트리가 끝나는 경우는 C와 V가 같은 지점에 연결된 경우입니다. 

두 지점이 연결되어 있다면 해당 경우의 비용을 출력하고 끝내줍니다. 

 

Find() 함수 코드입니다.

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}

X번째 connect 배열의 값이 X라면 바로 X를 return 해주면 됩니다.

아니라면 현재 배열의 값을 다시 Find() 함수에 넣어주면서 연결된 지점을 찾아가면 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

int p, w, c, v;
typedef struct line{
    int x;
    int y;
    int cost;
}line;
vector<line> Line;
int connect[1001];

bool cmp(line x, line y) {
    if (x.cost > y.cost) return true;
    else return false;
}

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
    int X = Find(x);
    int Y = Find(y);
    connect[X] = Y;
}

void solve() {
    for (int i = 1; i <= p; i++) connect[i] = i;
    for (int i = 0; i < Line.size(); i++) {
        int x = Find(Line[i].x);
        int y = Find(Line[i].y);
        int cost = Line[i].cost;
        if (x != y) {
            Union(x, y);
        }
        if (Find(c) == Find(v)) {
            cout << cost;
            break;
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> p >> w;
    cin >> c >> v;
    for (int i = 0; i < w; i++) {
        int x, y, cost;
        cin >> x >> y >> cost;
        Line.push_back({ x,y,cost });
    }
    sort(Line.begin(), Line.end(), cmp);
    solve();
    return 0;

}

 

 

질문 및 조언 댓글 남겨주세요