문제 요약
도넛 모양, 막대 모양, 8자 모양 그래프들이 존재한다.
새로운 정점을 하나 만든 뒤, 각 그래프의 임의의 정점으로 향하는 간선을 하나씩 추가했다. 이후 모든 정점의 번호가 섞인 상태에서 간선 정보만 주어진다.
다음 값을 순서대로 반환해야 한다.
- 새로 생성한 정점 번호
- 도넛 모양 그래프 개수
- 막대 모양 그래프 개수
- 8자 모양 그래프 개수
핵심 아이디어
각 그래프의 구조를 직접 순회할 필요가 없다. 모든 정점의 진입 차수와 진출 차수만 계산하면 그래프 종류를 구분할 수 있다.
| 대상 | 진입 차수 | 진출 차수 | 이유 |
|---|---|---|---|
| 생성 정점 | 0 | 2 이상 | 다른 그래프에서 들어오는 간선이 없고, 각 그래프에 간선을 하나씩 보냄 |
| 막대 그래프의 끝 정점 | 1 이상 | 0 | 더 이상 이동할 간선이 없는 종점 |
| 8자 그래프의 결합 정점 | 2 이상 | 2 이상 | 두 도넛의 결합 지점에서 두 방향으로 나가고 두 방향에서 들어옴 |
도넛 그래프는 모든 정점의 진입·진출 차수가 기본적으로 1이다. 따라서 생성 정점이 연결한 그래프 수에서 막대와 8자 그래프 수를 빼면 도넛 그래프 수를 구할 수 있다.
생성 정점 찾기
생성 정점은 원래 그래프들과 무관한 정점이다.
- 어느 정점에서도 생성 정점으로 향하는 간선이 없다.
- 모든 그래프에 하나씩 간선을 보내므로 진출 차수는 2 이상이다.
if in_degree[node] == 0 and out_degree[node] >= 2:
created_node = node막대 그래프 개수
막대 그래프에는 간선을 더 따라갈 수 없는 끝 정점이 하나 존재한다.
이 정점의 진출 차수는 0이다.
생성 정점이 막대 그래프의 시작 또는 중간 정점에 연결되더라도 종점의 진출 차수는 변하지 않는다. 따라서 진출 차수가 0인 정점 수가 막대 그래프 수와 같다.
if out_degree[node] == 0:
stick_count += 18자 그래프 개수
8자 그래프는 두 개의 도넛 그래프를 하나의 정점에서 결합한 구조다.
결합 정점에서는 두 간선이 나가고, 두 간선이 들어온다. 생성 정점에서 결합 정점으로 간선이 연결된 경우에도 진입 차수만 더 커질 뿐, 진입·진출 차수는 모두 2 이상이다.
if in_degree[node] >= 2 and out_degree[node] >= 2:
eight_count += 1생성 정점은 진입 차수가 0이므로 이 조건에 포함되지 않는다.
도넛 그래프 개수
생성 정점은 각 그래프에 간선을 정확히 하나씩 보낸다.
따라서 생성 정점의 진출 차수는 전체 그래프 개수다.
도넛 개수
= 생성 정점의 진출 차수
- 막대 그래프 개수
- 8자 그래프 개수Python 코드
from collections import defaultdict
def solution(edges):
in_degree = defaultdict(int)
out_degree = defaultdict(int)
nodes = set()
for start, end in edges:
out_degree[start] += 1
in_degree[end] += 1
nodes.add(start)
nodes.add(end)
created_node = 0
stick_count = 0
eight_count = 0
for node in nodes:
if in_degree[node] == 0 and out_degree[node] >= 2:
created_node = node
elif out_degree[node] == 0:
stick_count += 1
elif in_degree[node] >= 2 and out_degree[node] >= 2:
eight_count += 1
donut_count = out_degree[created_node] - stick_count - eight_count
return [created_node, donut_count, stick_count, eight_count]코드 설명
진입·진출 차수 계산
for start, end in edges:
out_degree[start] += 1
in_degree[end] += 1start -> end 간선 하나는 start의 진출 차수를 1 증가시키고, end의 진입 차수를 1 증가시킨다.
nodes 집합에는 간선에 등장한 모든 정점을 저장한다. 그래프의 모든 정점은 적어도 하나의 간선에 연결되어 있으므로, 이 집합을 순회하면 모든 정점을 검사할 수 있다.
조건 순서
if in_degree[node] == 0 and out_degree[node] >= 2:
created_node = node
elif out_degree[node] == 0:
stick_count += 1
elif in_degree[node] >= 2 and out_degree[node] >= 2:
eight_count += 1생성 정점은 진입 차수가 0이므로 막대 또는 8자 그래프 정점으로 중복 집계되지 않는다.
조건을 if - elif로 작성하면 한 정점을 한 유형에만 반영할 수 있다.
도넛 수 계산
donut_count = out_degree[created_node] - stick_count - eight_count생성 정점의 진출 간선 하나는 원래 그래프 하나를 의미한다.
막대와 8자 그래프의 수를 이미 구했으므로, 남은 그래프는 모두 도넛 그래프다.
정확성
생성 정점은 다른 그래프에서 들어오는 간선이 없으므로 진입 차수가 0이다. 또한 각 그래프에 하나의 간선을 연결하므로 진출 차수는 그래프 개수와 같고 2 이상이다. 따라서 알고리즘은 생성 정점을 정확히 찾는다.
막대 그래프에는 진출 간선이 없는 종점이 정확히 하나 존재한다. 다른 그래프 유형에는 진출 차수가 0인 정점이 없으므로 진출 차수 0인 정점 수는 막대 그래프 수와 같다.
8자 그래프에는 진입·진출 차수가 모두 2 이상인 결합 정점이 정확히 하나 존재한다. 도넛과 막대 그래프에는 이러한 정점이 없고 생성 정점은 진입 차수가 0이므로, 이 조건을 만족하는 정점 수는 8자 그래프 수와 같다.
생성 정점은 모든 그래프에 하나씩 간선을 보내므로 그 진출 차수는 전체 그래프 수다. 전체 개수에서 막대와 8자 그래프 수를 뺀 값은 도넛 그래프 수가 된다. 따라서 반환값은 문제에서 요구한 네 값을 정확히 나타낸다.
시간 복잡도
간선 수를 E, 서로 다른 정점 수를 V라고 하자.
간선을 한 번 순회해 차수를 계산하고, 정점을 한 번 순회해 유형을 판별한다.
O(E + V)공간 복잡도
정점별 진입 차수, 진출 차수, 정점 집합을 저장한다.
O(V)주의할 점
- 그래프 구조를 직접 DFS 또는 BFS로 분리할 필요가 없다.
- 생성 정점은 진출 차수가 정확히 2가 아니라
2 이상이다. - 8자 그래프의 결합 정점도 생성 정점에서 간선을 받을 수 있으므로 진입 차수 조건은
2 이상이다. - 막대 그래프는 진출 차수가
0인 정점으로 판단한다. - 도넛 그래프 수는 직접 세지 않고 전체 그래프 수에서 막대와 8자 그래프 수를 빼서 계산한다.
정리
이 문제는 복잡해 보이는 그래프 구조를 정점의 진입·진출 차수로 단순화하는 문제다.
생성 정점, 막대 종점, 8자 결합 정점의 차수 특징을 이용하면 그래프 순회 없이 O(E + V)에 답을 구할 수 있다.
