softeer : 거리합 구하기

https://softeer.ai/class/devcrew/study/resource/detail/description/6258?id=280&resourceId=328

Softeer - 현대자동차그룹 SW인재확보플랫폼

오늘도 수많은 삽질 끝에 해냈다!!

 

 

실패1 : 다익스트라

#include<iostream>
#include <vector>
#include <queue>
#include <climits>
#include <numeric>

using namespace std;

int n;
vector<vector<int>> times;

int diss(int node_index){
    vector<vector<int>> answer(n, vector<int>(2, INT_MAX)); // {distance, min으로 뽑혔는지 아닌지}
    answer[node_index][0] = 0;
    //answer[node_index][1] = 0;

    for(int i = 0; i<n; i++){
        // min뽑기
        int min_index;
        int min_value = INT_MAX;
        for(int j = 0; j<n; j++){
            if(answer[j][1] != 0 && min_value > answer[j][0]){
                min_index = j;
                min_value = answer[j][0];
            }
        }
        answer[min_index][1] = 0;
        // update
        for(int j = 0; j<n; j++){
            if(times[min_index][j] != 0){
                if(times[min_index][j] + answer[min_index][0] < answer[j][0]){
                    answer[j][0] = times[min_index][j] + answer[min_index][0];
                }
            }
            
        }
    }

    int result = 0;
    for(int i = 0; i<n; i++){
        result += answer[i][0];
    }
    
    return result;
    
}

int main(int argc, char** argv)
{
    cin >> n;
    times = vector<vector<int>>(n, vector<int>(n, 0));
    for(int i = 0; i<n-1; i++){
        int x, y, t;
        cin >> x >> y >> t;
        times[x-1][y-1] = t;
        times[y-1][x-1] = t;
    }

    for(int i = 0; i<n; i++){
        cout << diss(i)<<"\n";
    }
    
    
   return 0;
}

그래프의,, 길이?!??!! 하면서 Single Source Shortest Paths 구하는 방법을 이용했다

다익스트라를 쓴것같다..!

하지만 2초라는 에바적인 시간을 가지고 시간초과가,,,,,,,

 

 

 

실패2 : 바보

#include<iostream>
#include <vector>
#include <queue>
#include <climits>
#include <numeric>

using namespace std;

int n;
vector<vector<int>> times;

int sub_nodes(vector<vector<int>> edges, int root){
    int result = 1;
    for(int i = 0; i<n; i++){
        if(edges[root][i] != 0){
            edges[root][i] = 0;
            edges[i][root] = 0;
            result += sub_nodes(edges, i);
        }
    }
    return result;
}

int diss(int node_index){
    vector<vector<int>> edges = times;

    int answer = 0;

    queue<int> que;
    que.push(node_index);

    while(!que.empty()){
        int now_node = que.front();
        que.pop();
        for(int i = 0; i<n; i++){
            if(edges[now_node][i] != 0){
                int t = edges[now_node][i];
                edges[i][now_node] = 0;
                edges[now_node][i] = 0;
                int subns = sub_nodes(edges, i);
                answer += t * subns;
                if(subns > 1){
                    que.push(i);
                }
            }
        }
    }
    return answer;
}

int main(int argc, char** argv)
{
    cin >> n;
    times = vector<vector<int>>(n, vector<int>(n, 0));
    for(int i = 0; i<n-1; i++){
        int x, y, t;
        cin >> x >> y >> t;
        times[x-1][y-1] = t;
        times[y-1][x-1] = t;
    }

    for(int i = 0; i<n; i++){
        cout << diss(i)<<"\n";
    }
    
    
   return 0;
}

""트리"" 라는걸 이용했어야 했던것같다.

=> 어짜피 root부터, 특정 노트까지 가는길은 정해져있다! (사이클이 없음)

=> 즉 sub node개수를 가지고, 그냥 곱해서 더해주면 된다는 아이디어였다.

 

근데 이것두 똑같이,, 2초라는 시간이 나오면서 시간초과가 나왔다.

 

성공! : sub node개수 적극활용

#include<iostream>
#include <vector>
#include <queue>
#include <climits>
#include <numeric>

using namespace std;

long long n;
vector<vector<pair<long long, long long>>> times; // 인접리스트
vector<long long> subnodes;
vector<long long> rootdist;
vector<long long> answer;

vector<int> is_visit;

void sub_nodes(long long root){
    long long result = 0;
    for(long long i = 0; i<times[root].size(); i++){
        if(is_visit[times[root][i].first] == 0){
            is_visit[times[root][i].first] = 1;
            sub_nodes(times[root][i].first);
            result += subnodes[times[root][i].first];
        }
    }
    subnodes[root] = result + 1;
}

void dfs(long long node){
    for(long long i = 0; i<times[node].size(); i++){
        if(is_visit[times[node][i].first] == 0){
            is_visit[times[node][i].first] = 1;
            rootdist[times[node][i].first] += rootdist[node] + times[node][i].second;
            dfs(times[node][i].first);
        }
    }
}

void dfs2(long long node){
    for(long long i = 0; i<times[node].size(); i++){
        if(answer[times[node][i].first] == 0){
            is_visit[times[node][i].first] = 1;
            answer[times[node][i].first] = answer[node] + (times[node][i].second * (n - (2 * subnodes[times[node][i].first])));
            dfs2(times[node][i].first);
        }
    }
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    times = vector<vector<pair<long long, long long>>>(n);
    subnodes = vector<long long>(n, 1);
    rootdist = vector<long long>(n, 0);
    is_visit = vector<int>(n, 0);
    for(int i = 0; i<n-1; i++){
        long long x, y, t;
        cin >> x >> y >> t;
        times[x-1].push_back({y-1, t});
        times[y-1].push_back({x-1, t});
    }

    is_visit[0] = 1;
    sub_nodes(0);

    is_visit = vector<int>(n, 0);
    is_visit[0] = 1;
    dfs(0);

    answer = vector<long long>(n, 0);
    for(long long i = 0; i<n; i++){
        answer[0] += rootdist[i];
    }
    is_visit[0] = 1;
    dfs2(0);

    for(long long i = 0; i<n; i++){
        cout << answer[i]<<"\n";
    }
    
    
   return 0;
}

 

와,,, 와 진짜 이런 방법을 누가 생각한걸까?? 대단한 사람들이야..

 

내가 설명하는것보다,,,, softeer가 올려준 영상을 보는게 더 좋을거다

 

중요한건,, "인접한"노드가 root노드였을 때의 정답을 이용해주는것!!

 

https://www.youtube.com/watch?v=tvyDu2JBTpE&t=1152s

 

 

하,, 이런문제를 마주하면,, 절대 못풀것같은데ㅠㅠ