문제 링크
풀이 과정
•
본 문제는 코드로 풀이 과정을 대체합니다.
전체 코드
from collections import defaultdict
def solution(edges):
'''
1. 생성된 정점 -> 나가는 간선이 두 개 이상 존재 / 들어오는 간선 없음
2. 도넛 그래프 -> 모든 정점이 나가는 간선과 들어오는 간선이 한 개씩 존재
3. 8자 그래프 -> 하나의 정점이, 나가는 간선과 들어오는 간선이 각각 두 개씩 존재
4. 막대 그래프 -> 나가는 간선 + 들어오는 간선 모두 존재 안함(size=1)
또는, 나가는 간선이 1개 + 들어오는 간선 없음 OR 나가는 간선이 0개 + 들어오는 간선 1개
'''
answer = [0, 0, 0, 0]
max_node = 0 # 총 정점의 갯수
start_node = 0 # 생성된 정점 번호
in_edges = defaultdict(int) # 각 정점 별 들어오는 간선의 갯수
out_edges = defaultdict(int) # 각 정점 별 나가는 간선의 갯수
# 각 정점 별 간선 정보 초기화 및 총 정점 갯수 파악
for start, end in edges:
out_edges[start] += 1
in_edges[end] += 1
max_node = max([max_node, start, end])
# 생성된 정점 찾기
for node in range(1, max_node+1):
if (node not in in_edges) and (out_edges[node] >= 2):
start_node = node
break
answer[0] = start_node
# 총 그래프 갯수는 생성된 정점과 연결된 간선의 갯수와 같음
graph_num = out_edges[start_node]
# 생성된 정점과 연결된 간선을 제거 -> 유형 별 그래프 갯수를 파악하기 위함
for start, end in edges:
if start == start_node:
out_edges[start] -= 1
in_edges[end] -= 1
del out_edges[start_node] # 생성된 정점의 정보는 더 이상 필요 없음
# 8자 그래프 갯수 계산
eight_graph_num = 0
for node in range(1, max_node+1):
if node != start_node:
if (in_edges[node] == 2) and (out_edges[node] == 2):
eight_graph_num += 1
answer[-1] = eight_graph_num
# 막대 그래프 갯수 계산
stick_graph_num = 0
for node in range(1, max_node+1):
if node != start_node:
if (in_edges[node] == 0) and (out_edges[node] == 0) \
or (in_edges[node] == 1) and (out_edges[node] == 0):
stick_graph_num += 1
answer[2] = stick_graph_num
# 도넛 그래프 계산
answer[1] = graph_num - (eight_graph_num + stick_graph_num)
return answer
Python
복사