문제 링크

풀이 과정

• 본 문제는 코드로 풀이 과정을 대체합니다.

전체 코드

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