(Python) 프로그래머스 - 도넛과 막대 그래프

지난겨울 카카오 인턴을 지원하면서 이미 풀어보았던 문제였다.

그때는 인접 리스트를 구성해서 실제로 BFS 탐색을 돌리다가 시간 초과로 실패했었다.

이번에는 방법을 달리해서 풀이에 성공했다.

 

 

---

로직

각 노드의 들어오는 간선과 나가는 간선을 구하면 생각보다 쉽게 풀리는 문제다.

각 그래프마다 특정 규칙을 만족시키는 노드가 1개씩 존재한다.

정점은 들어오는 간선이 없으므로 들어오는 간선의 개수가 0이고, 나가는 간선의 개수는 문제의 조건에 따라서 2개 이상이다.

막대 모양 그래프는 이어진 노드중에 1개가 나가는 간선이 없는것이고, 8자 모양 그래프는 나가는 간선이 2개이면서 들어오는 간선은 2개 이상이다.

도넛 모양 그래프는 정점에서 나가는 간선의 개수 - 막대 모양 도형의 개수 - 8자 모양 도형의 개수를 하면 구할 수 있다.

 

 

최종 코드

def solution(edges):
    # 최대 노드 숫자 구하기
    max_node = max([i for sub in edges for i in sub])

    # 각 노드의 나가는 간선과 들어오는 간선을 리스트로 구성
    out_in = [[0, 0] for _ in range(max_node)]

    for start_node, end_node in edges:
        out_in[start_node - 1][0] += 1
        out_in[end_node - 1][1] += 1

    p_node = s_node = node_8 = 0

    for idx, node in enumerate(out_in):
        out_cnt, in_cnt = node
        # 나가는 간선이 없다면 막대모양
        if out_cnt == 0:
            s_node += 1
        # 나가는 간선이 2개 이상이고 들어오는 간선이 없다면 정점
        elif out_cnt >= 2 and in_cnt == 0:
            p_node = idx + 1
        # 나가는 간선이 2개이고 들어오는 간선이 2개 이상이면 8자모양
        elif out_cnt == 2 and in_cnt >= 2:
            node_8 += 1

    # 도넛 모양 = 정점에서 나가는 간선의 개수 - 막대모양 도형 개수 - 8자 모양 도형 개수
    d_node = out_in[p_node - 1][0] - s_node - node_8

    answer = [p_node, d_node, s_node, node_8]

    return answer