아직 계정이 없으신가요? 회원가입

Dev. Talk

[21년 재직자 대회 예선] 로드 밸런서 트래픽 예측 --- 이해가 안되는 현상...

회원사진7109417
89 views2021-11-12 00:17

풀이 방법은 각 밸런스 노드에 축적되는 값들을 계산한뒤 분배하는 식으로 카운트를 하는 방식입니다.


이때 특정 밸런스 노드의 parent 가 되는 밸런스 노드 들에서 분배가 끝나도록 했습니다. 밑의 코드는 정답이 출력되는데요, 


 if curr not in set_conquered:


부분이 없으면 오답이 나오게 됩니다.


이부분이 조금 이해가 안되는데요, parent 밸런스 노드들이 모두 분배가 끝났을때 queue 에 현재 밸런스 노드를 추가하기때문에 해당 노드의 방문 횟수는 1번이라고 생각했는데요, 위의 if 문이 없으면 오답 & 시간초과가 나는걸로 봐서 2번이상 방문을 하는것 같습니다. 해당 이유에 대해서 설명해주실수 있는 분이 계실까요??



import sys

N, K = [int(el) for el in sys.stdin.readline().split()]

list_node = []
for _ in range(N):
    row = [int(el) for el in sys.stdin.readline().split()]
    n_ch = row[0]
    list_ch = [el-1 for el in row[1:]]
    list_node.append((n_ch, list_ch))
dict_parent = {i:set() for i in range(N)}
for index, el in enumerate(list_node):
    _, list_ch = el
    for ch in list_ch:
        dict_parent[ch].add(index)

queue = [0]
call = [K] + [0]*(N-1)
set_conquered = set()
while queue:
    curr = queue.pop()
    if curr not in set_conquered:
        set_conquered.add(curr)
        n_ch = list_node[curr][0]
        list_ch = list_node[curr][1]
        for ch in list_ch:
            call[ch] += call[curr] // n_ch
        for i in range(call[curr] % n_ch):
            call[list_ch[i]] += 1
        for ch in list_ch:
            if list_node[ch][0]!=0 and dict_parent[ch].issubset(set_conquered):
                queue.append(ch)

print(" ".join([str(d) for d in call]))