| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
(원문이 폴란드어라서 gpt에게 번역 하청)
Bajtelandia의 컴퓨터 네트워크는 n개의 노드가 광섬유로 연결된 형태로 구성되어 있습니다. 광섬유 네트워크는 매우 조밀하지 않으며, 임의의 두 노드 간의 연결은 한 가지 방법으로만 가능합니다(직접 또는 간접적으로 연결됨). 이로 인해 일부 링크에서는 심각한 혼잡이 발생하여 정보 전송에 큰 지연이 발생합니다.
네트워크의 트래픽은 상당히 크며 기본적으로 일정한 속도로, 매 시간마다 각 노드는 이웃 노드와 패킷을 교환합니다. 링크의 부하란, 해당 링크를 통해 한 시간 동안 전송되는 패킷의 수로 정의됩니다(즉, 링크 양 쪽 끝에 위치한 노드 개수의 곱으로 계산됨). 회사는 네트워크의 부하가 너무 크지 않은지 확인하고, 네트워크를 개선하거나 확장할 필요가 있는지 파악하고자 합니다. 이를 위해 네트워크에서 가장 부하가 큰 링크의 부하가 얼마인지 알고 싶어합니다.
프로그램을 작성하여 네트워크에서 가장 부하가 큰 링크의 부하를 계산하세요.
입력
프로그램은 표준 입력에서 데이터를 읽어햐 합니다. 첫 번째 줄에는 네트워크 노드 수를 나타내는 정수 n (1 ≤ n ≤ 1,000)이 주어집니다. 다음 n - 1개의 줄에는 네트워크의 링크가 설명되며, 각 줄에는 한 개의 링크가 주어집니다. 링크 설명은 공백으로 구분된 두 개의 정수로 구성되며, 이들은 링크로 연결된 노드의 번호르 나타냅니다.
출력
프로그램은 표준 출력으로 결과를 작성해야 합니다. 출력은 네트워크에서 가장 부하가 큰 링크의 부하를 나타내는 하나의 정수여야 합니다.
풀이
문제에서 굵은 글씨 처리한 부분을 보면 임의의 두 노드가 유일한 경로로 연결된다고 했다. 그리고 입력에서 n개의 노드가 n - 1개의 간선으로 연결된 것을 보아 네트워크는 트리의 형태를 갖고 있다는 걸 알 수 있다.
링크의 부하는 "양쪽 끝에 위치한 노드 개수의 곱"이라고 표현되었는데, 정확히 뭘 말하는지 이해하기가 좀 어렵다. 하지만 예제 입력을 살펴보면 알 수 있다. 예제 입력의 트리는 아래 그림과 같다.
예제 출력은 6이다. 2와 3 사이의 링크가 최대치인 6의 부하를 갖고 있는데, 이건 그 간선을 끊었을 때 생기는 두 개의 트리가 갖는 각각의 노드 갯수를 곱한 값이다. 그럼 모든 간선에 대해 각 간선을 제거했을 때 생기는 서브 트리의 노드 수를 세어서 계산해보면 어떻게 될까? n개의 노드가 있을 때 n - 1개의 간선에 대하여 n개의 노드를 탐색해야 하기 때문에 시간복잡도는 O(n2)이다. 문제에서 n의 범위는 1,000 이하의 자연수라고 했기 때문에 충분히 1초 내에 연산이 가능하다.
하지만 트리의 성질을 이용하면 좀 더 빠르게 답을 구할 수 있다. 1을 루트로 정해놓고 루트로부터 탐색을 시작한다. 이때 각 노드에는 연결된 노드의 수와, 부모 노드, 각 노드를 루트로 하는 서브트리의 노드 수를 관리한다.
새 노드에 도착하면 연결된 노드의 수를 확인한다. 만약 1이라면 부모와 연결되어 있고 자식노드가 없는 것이므로 현재 노드의 서브트리 노드 수를 상위 노드로 넘겨준다. 1이 아니라면 연결된 노드를 확인하고 탐색을 시도한다. 탐색을 시도할 때마다 현재 노드의 연결된 노드 수를 1 감소시킨다.
이 탐색을 끝내면 모든 노드를 루트로 했을 때의 서브트리 노드 수가 기록된 배열이 완성된다. 각 서브트리 노드 값에서 N을 빼면 부모노드와의 링크를 끊었을 때 부모노드 쪽 서브트리의 수가 나오게 된다. 이렇게 두 값을 곱하며 최대값을 선형탐색하면 총 O(n)의 시간 복잡도로 탐색이 끝난다.
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
def solution():
N = int(input())
graph = [deque() for _ in range(N + 1)] # 트리를 관리하는 덱
subtree = [0] * (N + 1) # 현재 노드를 루트로 하는 서브트리의 정점 수
parent = [0] * (N + 1) # 현재 노드의 부모 노드
edge_cnt = [0] * (N + 1) # 현재 노드에 연결된 노드의 수
# 트리 생성
for _ in range(N - 1):
v, w = map(int, input().split())
graph[v].append(w)
graph[w].append(v)
edge_cnt[v] += 1
edge_cnt[w] += 1
# 트리 탐색(루트는 1)
now = 1
edge_cnt[1] += 1
while edge_cnt[now]:
# 연결된 노드의 수가 하나 뿐이면 부모 노드에 subtree 값 넘기고
# 부모 노드로 탐색 옮기기
if edge_cnt[now] == 1:
subtree[now] += 1
subtree[parent[now]] += subtree[now]
now = parent[now]
# 아니면 자식 노드로 탐색 이어가기
else:
# 탐색하려는 노드가 부모 노드라면 연결된 노드 덱의 맨 앞으로 보내기
if graph[now][-1] == parent[now]: graph[now].appendleft(graph[now].pop())
# 현재 노드의 연결된 노드 수 1 줄이고
# 탐색하려는 자식 노드의 부모 노드를 현재 노드로 바꾸기
# 탐색 노드를 자식 노드로 바꾸면서 부모 노드와 연결된 자식 노드 삭제
else:
edge_cnt[now] -= 1
parent[graph[now][-1]] = now
now = graph[now].pop()
res = 0
for i in range(2, N + 1):
res = max(res, subtree[i] * (N - subtree[i]))
print(res)
solution()
