[프로그래머스 Level 3] 등산코스 정하기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

 

결국 문제는 최소 길이로 된 등산로를 찾으면 되고, 이를 위해 최소 신장 트리를 먼저 만들어 모든 정점이 최소의 길이로 연결되도록 만들었다. 이후 시작점을 산봉우리로 설정하여 게이트를 찾도록 dfs를 돌렸다. 이 때 주의할 점으로는 같은 intensity이어도 산봉우리의 값이 가장 작은 걸 해야하기 때문에 summits를 먼저 정렬을 해줘야 한다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <memory.h>

using namespace std;

int parent[50001];

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

void uni(int x, int y) {
    x = find(x);
    y = find(y);
    parent[y] = x;
}

bool sameparent(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return true;
    else return false;
}

bool compared(vector<int> a, vector<int> b){
    return a[2]<b[2];
}

bool gate[50001];
bool summit[50001];

bool checked[50001];
int value[50001];
vector<pair<int,int>> path[50001];

int minV=987654321;
int vertx;

void dfs(int val, int node){
//    cout<<node<<" "<<val<<endl;
    checked[node]=true;
    if(gate[node]){
        if(minV>val){
            minV=val;
        }
        return;
    }
    for(int i = 0; i<path[node].size(); i++){
        if(!checked[path[node][i].first] && !summit[path[node][i].first])
            dfs(max(val,path[node][i].second), path[node][i].first);
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer;
    
    sort(paths.begin(), paths.end(), compared);
    
    for (int i = 1; i <= n; i++)parent[i] = i;
    for (int i = 0; i < paths.size(); i++) {
        if (!sameparent(paths[i][0], paths[i][1])) {
            uni(paths[i][0], paths[i][1]);
            path[paths[i][0]].emplace_back(paths[i][1],paths[i][2]);
            path[paths[i][1]].emplace_back(paths[i][0],paths[i][2]);
        }
    }
    for(int i = 0 ; i<gates.size(); i++){
        gate[gates[i]]=true;
    }
    for(int i = 0 ; i<summits.size(); i++){
        summit[summits[i]]=true;
    }
    sort(summits.begin(), summits.end());
    for(int i = 0 ; i<summits.size(); i++){
        int v = minV;
        dfs(-1, summits[i]);
        if(minV<v){
            vertx=summits[i];
        }
        memset(checked, false, sizeof(checked));
    }
    return answer={vertx, minV};
}