[Programmers] Level 2. 도넛과 막대 그래프

🔗 Problem Link

프로그래머스

---

❔Thinking

• 사이클을 이루는 도넛모양 그래프, 한줄로 이어진 막대 그래프, 동일한 도넛 모양 2개가 이어진 8자 모양 그래프의 각 개수를 반환한다.
• 그래프를 이루는 정점 이외에 하나의 생성점이 각 그래프와 연결되어 있고, 이 생성점도 찾아 반환한다.

---

💻Solution

from collections import defaultdict, deque

def solution(edges):
    answer = [0, 0, 0, 0]
    start, donut, bar, eight = 0, 1, 2, 3
    graph = defaultdict(list)
    # 0: 진출, 1: 진입
    degrees = defaultdict(lambda: [0, 0])

    for edge in edges:
        a, b = edge
        graph[a].append(b)
        degrees[a][0] += 1
        degrees[b][1] += 1

    for node, degree in degrees.items():
        outd, ind = degree

        if outd == 0:
            answer[bar] += 1
        elif outd == 2:
            if ind > 0:
                answer[eight] += 1
            else:
                answer[start] = node
                root = node
        elif outd > 2:
            answer[start] = node
            root = node

    answer[donut] = degrees[root][0] - answer[bar] - answer[eight]

    return answer

---

🗝️keypoint

1. 각 그래프에서 유일하게 등장하는 정점의 특징을 파악하고, 그 특징으로 해당 그래프의 개수를 확인한다.
   1. 막대 그래프 : 마지막 정점은 진입 차수 = 1, 진출 차수 = 0이다.
   2. 8자 모양 그래프 : 진출 차수 = 2, 진입 차수 0 이상이다.
   3. 도넛 모양 그래프 : 생성점에서의 진출 차수 (=총 그래프 개수)에서 다른 두 그래프의 수를 빼면 구할 수 있다.
2. defaultdict는 key값을 매번 확인하지 않더라도 dict에 값을 저장할 수 있고, lambda를 활용해 특정 구조를 만들 수 있다.