그래프 이론에는 머리(head)와 발(feet)이라는 두 종류의 정점으로 구성된 특수한 형태의 그래프가 있습니다. 이 그래프는 머리 정점을 정확히 하나만 가지며, 머리를 각 발에 연결하는 k개의 간선으로 이루어집니다. 따라서 무방향·비가중치 그래프가 주어졌을 때, 이 그래프의 정점 분리(vertex disjoint) 부분 그래프 안에서 이러한 특수한 그래프를 모두 찾아내야 합니다. 두 그래프가 공통으로 가지는 정점이 하나도 없을 때, 두 그래프는 정점 분리되어 있다고 정의합니다.
예를 들어 입력이 아래 그림과 같고,
노드의 수(n) = 5, 발의 수(t) = 2라면 출력은 5가 됩니다. 즉, 주어진 그래프의 정점 분리 부분 그래프 가운데 이러한 특수한 그래프는 총 5개 존재할 수 있습니다.
해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- G := n+1개의 빈 리스트를 담는 새로운 리스트(인접 리스트)를 생성합니다.
- edges의 각 항목에 대해 다음을 수행합니다.
- s := item[0]
- d := item[1]
- G[s]의 끝에 d를 삽입합니다.
- G[d]의 끝에 s를 삽입합니다.
- visit := 새로운 맵(딕셔너리)을 생성합니다.
- i를 0부터 n까지 반복하며 다음을 수행합니다.
- v := G[i]
- v의 크기가 1이면(차수가 1인 정점, 즉 '발'):
- s := v[0]
- s가 visit에 없으면 visit[s] := [i]
- 그렇지 않으면 visit[s]의 끝에 i를 추가합니다.
- v의 크기가 0이면(고립된 정점): n := n - 1
- tmp := 0
- visit의 각 키 k에 대해 다음을 수행합니다.
- x := visit[k]의 크기 - t
- x > 0이면 tmp := tmp + x
- n - tmp를 반환합니다.
알고리즘 동작 원리
이 알고리즘의 핵심은 각 정점의 차수(degree)를 활용하는 것입니다.
- 차수가 1인 정점은 다른 정점 하나에만 연결되어 있으므로 '발'의 역할을 합니다. 이러한 발들을 연결된 이웃 정점(잠재적인 '머리')을 키로 하여 visit 맵에 그룹화합니다.
- 차수가 0인 정점은 어느 그래프에도 속하지 못하는 고립 노드이므로 전체 노드 수에서 제외합니다.
- 하나의 머리에 연결된 발의 수가 t를 초과하면, 초과된 발(x = 발의 수 - t)은 하나의 특수 그래프를 완성하는 데 사용할 수 없으므로 최종 개수에서 차감합니다.
예제
다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(n, t, edges):
G = [[] for _ in range(n + 1)]
for item in edges:
s, d = map(int, item)
G[s].append(d)
G[d].append(s)
visit = {}
for i in range(n):
v = G[i]
if len(v) == 1:
s = v[0]
if s not in visit:
visit[s] = [i]
else: visit[s].append(i)
elif len(v) == 0:
n -= 1
tmp = 0
for k in visit:
x = len(visit[k])-t
if x > 0:
tmp += x
return n - tmp
print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))
입력
6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]
출력
5
이 예제에서 노드 1과 2는 머리 4에 연결된 발이고, 노드 5는 머리 3에 연결된 발입니다. t = 2이므로 머리 4는 발 2개와 함께 하나의 특수 그래프를 온전히 이룹니다. 고립된 노드는 전체 개수에서 제외되고, 발이 부족한 그룹은 추가로 차감되지 않으므로 최종 결과는 5가 출력됩니다.