[백준][C++] 11085번: 군사 이동 <231>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

11085번: 군사 이동

생각의 흐름

C++에서의 Class를 간만에 작성해서.... 오래걸린 문제....

 

맨 처음에 문제를 읽고 든 생각은, 꼭 최단경로는 아니여도 된다는 점 이다.

그냥 지나간 길의 모든 너비중에서 가장 좁은 길의 너비를 최대화하는 경로를 선택하는 것 이였다.

 

우선 경로의 너비를 기준으로 가장 너비가 넓은 경로부터 선택할 것 이다.

따라서 Line 이라는 class를 만들어 vector안에 다 받은 후, sort를 적용시킨다. 내림차순으로 정렬하여 큰수부터 나오도록 한다.

 

이후 vector에 담겨있는 Line을 확인해가면서 start, end 지점을 확인한다.

각 start 와 end의 group을 확인하여 

1) 같은 그룹이 아니라면 -> join으로 동일 그룹으로 만듬

2) 같은 그룹이라면 -> 그냥 pass

 

이렇게 매번 반복하면서 c, v의 group을 확인했을때 같은 경우가 나온다면, 이때 출력을 하고 끝내면 된다!

 

주석을 좀더 참고하면서 코드를 보면 더 이해가 잘될 것 입니다!

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 1001

int p, w, c, v;
int parent[MAX];

class Line{
public:
    int x;
    int y;
    int cost;
public:
    Line(int _x, int _y, int _cost) : x(_x), y(_y), cost(_cost) {}

    bool operator < (const Line& n) const {
        return this->cost > n.cost;
    }
};

int find(int n) {
    if(parent[n] == n) return n;
    return parent[n] = find(parent[n]);
}

void join(int a, int b) {
    int ap = find(a);
    int bp = find(b);

    if(ap != bp) {
        parent[ap] = bp;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> p >> w >> c >> v;
    vector<Line> adj;

    for(int i = 0; i < MAX; i++) {
        parent[i] = i;
    }

    for(int i = 0; i < w; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        adj.push_back(Line(start, end, cost));
    }

    sort(adj.begin(), adj.end());

    for(int i = 0; i < adj.size(); i++) {
        Line &line = adj[i];
       	// //현재 간선이 잇는 두 정점 x, y
        int xP = find(line.x);
        int yP = find(line.y);
        int cost = line.cost;

        //Union-Find로 사이클이 발생하는지 확인, 사이클이 없다면 같은 그룹으로 만들기
        if(xP != yP) {
            join(line.x, line.y);
        }
        
        // 시작지점과 도착지점의 그룹의 같아짐 => 경로를 찾은 경우 => 이때의 값을 출력
        if(find(c) == find(v)) {
            cout << line.cost;
            break;
        }
    }

    return 0;
}