Softeer - 로드 밸런서 트래픽 예측

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=629 

Softeer

 

요는 로드 밸런서 자체를 구현하는 게 아니라, 예측 이다.

임의의 노드에 대한 계산을 하기 전에, 그 노드의 부모노드가 계산되었는지 확인이 필요하다.

하나의 노드를 처리한 후, 그 노드의 자식노드를 처리할 때, 다른 부모노드의 영향을 받는지 확인하면 된다.

이렇게 하면, 각 노드는 자식노드로 단 한번씩만 전파된다.

 

- 시도1 : 로드 밸런서 자체를 만들어서 실행. -> 타임아웃..

- 시도2 : 로드 밸런서 실행시키면서 반복구간을 찾고, 반복구간 길이를 가지고 계산하기. -> 타임아웃..

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

using namespace std;


class Node {
public:
	Node(int c) : v(vector<int>(c)) {
		r = c;
		x = 0;
	}

	int x;
	int r;
	vector<int> v;
};


void f(vector<Node>& node, vector<vector<int>>& parent, vector<long long>& count, long long k) {
	queue<int> que;
	que.push(0);

	vector<bool> visit(node.size());
	count[0] = k;

	while (!que.empty()) {
		int cur = que.front();
		que.pop();

		int n = node[cur].r;
		if (visit[cur] || n == 0)
			continue;

		bool ready = true;
		for (int i = 0; i < parent[cur].size(); ++i) {
			if (!visit[parent[cur][i]]) {
				ready = false;
				break;
			}
		}

		if (!ready) continue;
		visit[cur] = true;

		long long q = count[cur] / n;
		int r = count[cur] % n;

		vector <long long> c(n, q);
		for (int& i = node[cur].x, j = 0; j < r; ++j) {
			++c[i];
			i = (i + 1) % n;
		}

		for (int i = 0; i < n; ++i) {
			int t = node[cur].v[i];
			count[t] += c[i];
			if (node[t].r)
				que.push(t);
		}
	}
	return;
}


int main() {
	int n;
	long long k;
	cin >> n >> k;

	vector<Node> node;
	vector<vector<int>> parent(n, vector<int>());

	for (int i = 0; i < n; ++i) {
		int c;
		cin >> c;
		node.push_back(Node(c));
		for (int j = 0; j < c; ++j) {
			cin >> node[i].v[j];
			--node[i].v[j];
			parent[node[i].v[j]].push_back(i);
		}
	}

	vector<long long> count(n, 0);


	f(node, parent, count, k);

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

	return 0;
}