[2024 KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프

1. 풀이

from collections import deque

def solution(edges):
    answer = []
    
    max_num = 0
    graph = [[] for _ in range(1000001)]
    # 만들어진 노드는 들어오는 edge가 없다. 이를 체크하기 위한 노드다.
    not_end_list = [True for _ in range(1000001)]
    
    # graph를 생성한다.
    for edge in edges:
        start, end = edge

        graph[start].append(end)
        not_end_list[end] = False

        max_num = max(max_num, start, end)
    
    # 임의로 만들어진 노드는 들어오는 edge가 없어야 하며 2개 이상의 나가는 edge가 있어야 한다.
    created_node = 0
    for index, value in enumerate(not_end_list[:max_num+1]):
        if value and len(graph[index]) > 1:
            created_node = index
            break
    
    result = [created_node, 0, 0, 0]
    
    # bfs로 그래프를 순회하며 result의 값을 조정한다.
    visited = [False for _ in range(max_num+1)]
    for start in graph[created_node]:
        queue = deque([start])
        node = 1
        edge = 0
        
        while queue:
            now = queue.popleft()
            for next in graph[now]:
                edge += 1
                if not visited[next]:
                    visited[next] = True
                    queue.append(next)
                    node += 1
        
        if edge == node: 
            result[1] += 1
        elif edge == node-1:
            result[2] += 1
        else:
            result[3] += 1
        
    return result

---

프로그래머스