n개의 도시가 있고, 이 도시들을 연결하는 여러 개의 도로가 있다고 가정해 보겠습니다. 각 roads[i] = [u, v]는 도시 u와 도시 v 사이에 양방향 도로가 존재함을 의미합니다.
여기서 네트워크 랭크(network rank)란 두 도시 중 하나에 직접 연결된 도로의 총 개수를 말합니다. 단, 하나의 도로가 두 도시 모두에 직접 연결되어 있는 경우에는 한 번만 계산합니다. 그리고 최대 네트워크 랭크(maximal network rank)는 서로 다른 도시 쌍들 중에서 가장 큰 네트워크 랭크 값을 의미합니다.
예를 들어 다음과 같은 입력이 주어졌을 때,
출력은 5가 됩니다. 도시 1과 도시 2를 기준으로 직접 연결된 도로를 합산하면 총 5개이기 때문입니다.
해결 접근 방법
이 문제를 해결하기 위해 다음과 같은 단계를 따릅니다.
- n := 노드(도시)의 개수
- s := 새로운 집합(set) 생성
- d := 딕셔너리(맵) 생성, 키가 없으면 기본값 0 반환
- roads의 각 간선 (x, y)에 대해:
- d[x] := d[x] + 1
- d[y] := d[y] + 1
- 집합 s에 쌍 (x, y) 삽입
- ans := 0으로 초기화
- l := 0부터 n까지의 리스트 생성
- l을 노드별 차수(degree)를 기준으로 내림차순 정렬
- threshold := d[l[0]]과 d[l[1]] 중 최솟값
- i를 0부터 l의 크기 - 1까지 반복:
- j를 i+1부터 l의 크기 - 1까지 반복:
- 만약 d[l[j]] < threshold라면 내부 반복문 종료
- curr := d[l[i]] + d[l[j]]
- (l[i], l[j]) 또는 (l[j], l[i])가 집합 s에 존재하면 curr에서 1 감소
- ans := ans와 curr 중 최댓값
- j를 i+1부터 l의 크기 - 1까지 반복:
- ans 반환
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
def solve(roads):
nodes = set()
s = set()
d = defaultdict(int)
for x,y in roads:
nodes.update([x,y])
d[x]+=1
d[y]+=1
s.add((x,y))
ans = 0
n = len(nodes)
l = list(range(n))
l.sort(key=lambda x:d[x], reverse = True)
threshold = min(d[l[0]],d[l[1]])
for i in range(len(l)-1):
for j in range(i+1,len(l)):
if d[l[j]]<threshold:
break
curr = d[l[i]]+d[l[j]]
if (l[i],l[j]) in s or (l[j],l[i]) in s:
curr-=1
ans = max(ans,curr)
return ans
roads = [(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]
print(solve(roads))
입력
[(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]
출력
5
코드 설명
이 알고리즘은 먼저 각 도시의 차수(연결된 도로 수)를 계산한 후, 차수가 높은 도시부터 내림차순으로 정렬합니다. 그다음 상위 두 도시의 차수 합을 임계값(threshold)으로 설정하여, 임계값보다 작은 차수를 가진 도시 조합은 미리 탐색을 중단함으로써 불필요한 연산을 줄입니다. 두 도시가 서로 직접 연결되어 있는 경우에는 해당 도로가 중복 계산되므로 1을 빼주어 정확한 네트워크 랭크를 구합니다. 이러한 최적화 덕분에 모든 도시 쌍을 완전 탐색하는 것보다 효율적으로 최대 네트워크 랭크를 찾을 수 있습니다.