[Softeer] 21년 재직자 대회 예선 - 로드밸런서 트래픽 예측

문제

<배경>

자율주행 기술은 현대 컴퓨팅의 여러 최첨단 기술에 의존하지만, 이것이 가능하게 하려면 자동차에서 할 수 없는 복잡한 계산과 실시간 도로 정보 확인 등을 중앙 서버에서 빠르고 신속하게 처리할 수 있어야 한다.

이를 위해서 흔히 사용되는 방법은 요청(request)을 처리하는 많은 워커 노드(worker node)를 두고, 로드 밸런서(load balancer)가 이들 워커 노드에 트래픽을 적절히 분산시키는 것이다.

 

현재 총 $N$개의 서버가 있다. 이 문제에서 서버는 로드 밸런서 또는 워커 노드를 의미하며,

각각의 서버가 동시에 로드 밸런서이면서 워커 노드일 수는 없다. 

$i$번째 서버가 트래픽을 분산시키는 서버들은 중복을 포함하여 총 $r_i$개 있다.

$r_i = 0$이면 $i$번째 서버는 워커 노드로, 요청을 직접적으로 처리한다.

$r_i > 0$이라면, $i$번째 서버는 로드 밸런서로, 아래와 같은 라운드-로빈 (Round-Robin) 방식으로 트래픽을 분산한다.

• 각각의 로드 밸런서에는 정수형 변수 $x_i$가 있다. 처음에 $x_i = 1$이다.
• 로드 밸런서로 요청이 하나 들어오면, $p_{i, x_i}$번 서버로 트래픽을 전달하고, $x_i$의 값을 $(x_i mod r_i) + 1$로 바꾼다.

1번 서버는 루트 로드 밸런서로, 웹 서버로의 모든 요청은 루트 로드 밸런서로만 들어온다.

주어진 트래픽 분산 규칙은 효율적인 분산이 가능하도록 아래 두 조건을 만족한다.

• 트래픽이 같은 로드 밸런서를 여러 번 거치지 않도록,  $i \rightarrow p_{i,j}$간선들로 구성된 그래프에서 사이클이 존재하지 않는다.
• 1번 서버에 무한히 많은 요청을 보낸다면 모든 서버로 요청이 적어도 1개 이상은 전달된다.

총 $K$개의 요청이 들어왔다고 할 때, 각 서버로 들어오는 요청의 개수가 몇 개인지를 구하는 프로그램을 작성하라.

 

<입력>

 

<출력>

$N$개의 정수를 공백 하나씩을 사이로 두고 출력한다. $i(1 \leq i \leq N)$번째 정수는, $i$번 서버가 받는 요청의 개수이다.

 

<예시>

아래와 같은 구조가 있을 때,

6번의 요청 전달 모습은 아래와 같다.

---

풀이

설명이 복잡해 보이긴 하지만, 그냥 매번 자신한테서 나가는 방향의 경로를 순차적으로 돌면서 선택한다고 생각하면 된다.

 

먼저 입력 처리를 해준다.

노드 번호가 1부터 시작하기 때문에 0번 인덱스는 0을 넣어 인덱스와 노드번호가 일치하도록 했다.

n,k = map(int,input().split())
dag = [[0]]
for i in range(n):
    temp = list(map(int,input().split()))
    dag.append(temp)

위 문제의 경우 dag는 아래처럼 된다.

[[0], [3,2,5,8], [0], [0], [0], [3,2,4,3], [0], [0], [2,6,7]]

 

 

이 문제는 위상정렬(topological sort)을 알고 있어야한다.

위상정렬은 게임에서 어떤 스킬을 배워야만 다른 스킬을 배울 수 있는 것 같은 선행 관계가 정해져 있을 때, 뭘 먼저 해야하는지 순서대로 정렬하는 방법이다.

 

노드로 들어오는 화살표의 수를 indegree라고 하는데 이 값이 0인 노드들부터 처리하면 된다.

즉, indegree가 0인 노드를 큐에 넣고 하나씩 꺼내면서 해당 노드와 연결된 간선을 제거해 나가면, 새롭게 indegree가 0이 된 노드들이 다시 큐에 들어오고 이를 반복하는 방식으로 전체 정점을 순서대로 나열할 수 있다.

 

따라서 위상정렬을 먼저 구현해야한다.

각 노드의 indegree를 계산하는 함수 caldegree와 위상정렬을 구현하는 tsort함수를 만들었다.

dag[node][0]는 '그 노드의 자식노드의 수'를 의미한다는 것을 생각하고 아래 코드를 보면 이해가 쉬울 것이다.

def calindegree(dag):
    indegree = [0] * (n+1) #각 노드의 indegree 저장 용
    for i in range(1, n+1): #각 노드에 대해
        for j in range(1, dag[i][0]+1):# i 번째 노드에서 나가는 화살표 수 만큼 반복
            indegree[dag[i][j]] += 1 # i번째 노드에서 나가는 화살표가 가리키는 노드의 indegree를 1증가
    return indegree

def tsort(dag): #위상정렬
    indegree = calindegree(dag)
    stack = []
    for i in range(1,n+1):
        if indegree[i] == 0: #indegree가 0인 노드들 스택에 넣기
            stack.append(i)
    
    ordering = []
    while stack:  #스택이 빌 때까지
        node = stack.pop() #indegree가 0인 노드 하나 뽑아서
        ordering.append(node)
        for i in range(1, dag[node][0]+1): #그 노드의 자식노드들에 대해
            child = dag[node][i]
            indegree[child] -= 1   #indegree를 하나씩 줄인다
            if indegree[child] == 0: #indegree가 0이 되면 제거
                stack.append(child)
    return ordering

 

 

이제 트래픽을 분산시키는 알고리즘을 짜보자.

이 알고리즘은 간단하다.

먼저 트래픽을 자식노드 개수로 정확히 나눠떨어지면 그렇게 나누면 되고,

나머지가 있다면 하위 노드에 순서대로 1씩 배정해주면 된다.

ordering = tsort(dag)

traffic = [0]*(n+1)
traffic[1] = k
for i in range(n):
    node = ordering[i]
    request = raffic[node]
    if dag[node][0] == 0: #가장 끝 노드
        continue
    quotient = request//dag[node][0] #몫
    remainder = request%dag[node][0] #나머지
    for j in range(1, dag[node][0]+1):
        child = dag[node][j]
        traffic[child] += quotient
    for j in range(1, remainder+1):
        child = dag[node][j]
        traffic[child] += 1

for i in range(1, n):
    print(traffic[i], end=' ')
print(traffic[n])

 

이 문제는 

 

1. 위상정렬 구현

2. 밸런서 구현

 

이렇게 두 개의 메인 구현이 있는 문제였다.

위상정렬을 알았다면 쉽게 풀 수 있는 문제이다.