소프티어 로드 밸런서 트래픽 예측 (Python)

로드 밸런서는 트리로 구성되어 부모 노드로부터 트래픽을 분산받게 되는데 현재 노드는 부모 노드로부터 받을 수 있는 모든 트래픽을 받고 다음 자식 노드로 분배하도록 구현해야 합니다. 예를 들면, 다음의 예시가 있습니다.

단순히 DFS로 구현했을 때, 1번에 999가 들어온다면 9번과 10번에는 223, 221개씩 분배하게 됩니다. 왜냐하면 2번이 처리할 때, 1번으로부터 오는 333번을 9번과 10번에 분배하면 167, 166번이 들어가고 다음 5번으로부터 오는 111개는 56번과 55번으로 나눠지기 때문에 최종 223, 221로 나눠 원하는 정답을 얻을 수 없게 됩니다.

 

따라서 위상 정렬 아디이어를 이용하여 코드를 구현하는 방법으로 문제를 해결할 수 있습니다. indegree 배열을 이용하여 현재 노드의 부모로부터 트래픽을 받은 후 현재 노드의 차수를 제거하고 모든 차수가 제거되면 다음 자식 노드로 넘어갈 수 있는 로직을 구현하기 쉽기 때문입니다.

 

	import sys
	n,k = map(int,input().split())
	tree = {}
	indegree = [0 for _ in range(n+1)]
	for i in range(1,n+1):
	x = list(map(int,input().split()))
	if x[0]:
	tree[i]=x[1:]
	for x_ in x[1:]:
	indegree[x_]+=1
	answer = [0 for _ in range(n+1)]
	answer[1]=k
	stk = [[1,k]]
	while stk:
	node,req = stk.pop()
	if node in tree.keys():
	cyc, remain = req//len(tree[node]), req%len(tree[node])
	for i, nxt in enumerate(tree[node]):
	if indegree[nxt]: # 간선이 남아있는 경우 덧셈만 해준다
	indegree[nxt]-=1
	if i<remain:
	answer[nxt]+=cyc+1
	else:
	answer[nxt]+=cyc
	if not indegree[nxt]: # 간선이 없는 경우 다음 자식 노드에 트래픽을 분산할 준비를 한다
	stk.append((nxt,answer[nxt]))
	print(*answer[1:],sep=' ')

view raw softeer_load_balancer.py hosted with ❤ by GitHub