softeer : 로드 밸런서 트래픽 예측

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

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

 

열심히 삽질끝에 해냈다~~

 

이 문제의 핵심은 topological sort를 이용하는것!

 

처음에는 시뮬레이션 문제로 접근했다! 진짜 k번씩 반복을 돌려서 각 노드에 하나씩 누적시키는.......

근데 일단 k의 범위가 long long까지 가서 오래걸리는것뿐만 아니라

그래프가 커지면 너무 곤란해진다! 타고타고  내려가야하기 때문이다

그냥 구현자체를 잘못했을 수 있지만, 아마 시간문제도 있었을것같다.

 

두번째로는 그럼 노드를 타고타고 내려가면서, outgoing edge개수만큼 나눠주면 되지 않을까? 하는 생각이었다.

근데,,,, 이럴때의 문제는 트래픽이 정확히 다음노드 개수로 안나뉘어 졌을 때, 문제가 생긴다!

이런경우 왼쪽부터 하나씩 1을 더 분배해 줘야 하는데, 댑다 bfs 또는 dfs로 그래프를 탐색하면서 나눠주면, 여기서 좀 꼬이게된다..

(incoming edge가 두개인 노드의 경우, 트래픽 덩어리를 두번받게 되는데 이 때 단순히 다음 노드 개수 (예를 들면 3)으로 나누고, 순서대로 나머지를 보내는 방법으로는 전체적인 순서를 못지킨다!

첫번째 트래픽 덩어리가 901이어서 301 300 300 을 보내고, 두번째 트래픽 덩어리도 901이어서 301 300 300을 보냈다고 생각하면,,,,,,,,,,, 최종적으로 602 600 600을 보내는 꼴이 된다! 하지만 문제 설명대로라면 601 601 600을 보내야 하는게 맞다)

 

이걸 방지하기 위해 topological sort로 순서를 명확히 해줘야한다!

지금 노드에서 트래픽 덩어리를 다음 노드로 보내는 동작을 한번한 하도록 강제할 수 있어야한다.

 

문제에서 사이클이 없다고 정해줬고, 또 루트노드에서 모든 노드에 접근할 수 있다고 정해줬기 때문에 루트를 시작으로 하는 topological sort를 한번만 하면 된다ㅎㅎ

https://usowelcome.tistory.com/111

Topological Sort

 

그리고 트래픽 분산은 topological sort된 순서대로 해주면 된다! 굿굿

 

---

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> servers; // servers[i] 에 연결리스트 형태로,,,
vector<int> lists; // topological sort 결과
int n;
long long int k;
int time_stamp = 0;

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

void dfs(int node, vector<vector<int>>* nodes){
    for(int i = 0; i<servers[node].size(); i++){
        int next_node = servers[node][i];
        if((int)((*nodes)[next_node-1].size()) > 1){
            continue;
        }
        (*nodes)[next_node-1].push_back(time_stamp);
        time_stamp++;
        dfs(next_node, nodes);
        (*nodes)[next_node-1].push_back(time_stamp);
        time_stamp++;
        
    }
}

void topological_sort(){

    vector<vector<int>> nodes(n); // {index, start, end}
    for(int i = 0; i<n; i++){
        nodes[i].push_back({i+1});
    }
    // root node(1) 에서 모든곳에 연결됨!
    nodes[0].push_back(time_stamp);
    time_stamp++;
    dfs(1, &nodes);
    nodes[0].push_back(time_stamp);

    sort(nodes.begin(), nodes.end(), comp);
    for(int i = 0; i<n; i++){
        lists.push_back(nodes[i][0]);
    }
}

vector<long long> balance(){
    vector<long long> answer(n+1, 0);
    answer[1] = k;
    for(int i = 0; i<n; i++){
        int index = lists[i];
        if(servers[index].size() == 0){
            continue;
        }
        long long div = answer[index] / (long long)servers[index].size();
        long long mod = answer[index] % (long long)servers[index].size();
        for(int j = 0; j<servers[index].size(); j++){
            answer[servers[index][j]] += div;
            if(j < mod){
                answer[servers[index][j]] += 1;
            }
        }
    }
    return answer;
}


int main(int argc, char** argv)
{

    
    cin >> n >> k;
    servers = vector<vector<int>>(n+1);
    for(int i = 1; i<=n; i++){
        int r;
        cin >> r;
        for(int j = 0; j<r; j++){
            int temp;
            cin >> temp;
            servers[i].push_back(temp);
        }
    }

    topological_sort();

    
    vector<long long> answer = balance();

    for(int i = 1; i<=n; i++){
        cout << answer[i]<<" ";
    }
    

   return 0;
}