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

                                    👓 내 생각
👉 각각의 점을 직접 방문하여 point와 edge 수를 계산하려고 함

👉 start point가 가장 나가는 정점이 많은 것으로 해석
❌ 보장되지 않음

👉 그래프 관리를 접점으로 함
ex)
graph:  {
    4: [11, 2, 8],
    1: [12], 8: [3],
    12: [7], 7: [11],
    9: [6], 10: [11],
    6: [10],
    3: [5, 8],
    11: [1, 9],
    5: [3]
}
❌ in bound가 없어서 알고리즘이 복잡해질 수 있음

                                    1. 시작점: inbound = 0, only outbound >= 1
👉 문제에서 그래프의 합이 2이상이라 하였으므로 outbound >= 2로 설정

2. donut: inbound = 1, out bound 1

3. line: inbound = 1, out bound 0

3. eight: inbound = 2, outbound 2

                                    edge를 고려한 전략

1. 전체 그래프의 수 : edge 노드의 outbound 수
👉 우리는 두 개만 구하면 하나를 자동으로 알 수 있다.

2. eight id node: edge를 제외하면 유일하게 outbound가 2이다.

3. line id node: 유일하게 out bound가 존재하지 않는다.

                                    👉 line 그래프의 판별 조건이 변경

- edge가 아니다
- inbound가 반드시 하나 이상일 것 (edge노드에 의해 2가 될 수 있음)
- outbound는 0일 것

                                    def solution(edges):
    out_graph = {}
    in_graph = {}

    if len(edges) == 1:
        return [1, 0, 1, 0]

    # find max point & set graph
    max_point = -999
    for u, v in edges:
        max_point = max(max_point, u, v)
        out_graph[u] = out_graph.get(u, 0) + 1
        in_graph[v] = in_graph.get(v, 0) + 1

    # find start
    start = -1
    for u, v in edges:
        outbound = out_graph.get(u, 0)
        inbound = in_graph.get(u, 0)
        if outbound >= 2 and inbound == 0:
            start = u

    total_graph = out_graph[start]

    stick = 0
    eight = 0
    # find stick and eight
    for i in range(1, max_point + 1):    # v가 체크가 안되네 ...
        if i == start:
            continue
        inbound = in_graph.get(i, 0)
        outbound = out_graph.get(i, 0)
        if outbound == 0 and inbound >= 1:
            stick += 1
            continue

        if outbound == 2:
            eight += 1
            continue

    donut = total_graph - (stick + eight)

    answer = [start, donut, stick, eight]

    return answer

                                    def is_donut(key, graph):
    # 한번씩 거치며 자기 자신에게 돌아온다.
    # 정점 수와 간선 수가 일치한다.

    visited = set()

    point = 0
    edge = 0

    while 1:
        if key in visited:
            break

        visited.add(key)
        point += 1

        next = graph[key]
        if len(next) > 1:
            return [set(), False]
        key = next[0]
        edge += 1

    if point == edge:
        return [visited, True]

    # return [Set(정점들), True/False]

def is_direct(key, graph):
    # 간선이 아에 없거나
    # 간선이 하나만 존재하며 no-cycle
    # return [Set(정점들), True/False]

    visited = set()

    point = 0
    edge = 0

    while 1:
        if len(graph[key]) > 1:
            return [set(), False]

        if key not in graph: # 간선이 없으면 포함 x -> 끝점
            visited.add(key)
            point += 1
            break

        visited.add(key)
        point += 1

        key = graph[key][0]
        edge += 1

    if point - edge != 1:
        print("in direct, point - edge != 1")
        return [set(), False]

    return [visited, True]

def is_eight(key, graph):

    identifier = set()
    visited = {}

    point = 0
    edge = 0

    while 1:
        if visited[key] == 2:
            break

        if key not in visited:
            visited[key] = 1

        else:
            visited[key] += 1

        point += 1

        # check two path
        nexts = graph[key]

        if len(nexts) > 2:
            print("something wron ...")
            return [set(), False]

        if len(nexts) == 2:
            for nxt in nexts:
                if nxt == key:
                    continue
                key = nxt
            edge += 2
        else:
            key = nexts[0]
            edge += 1

def solution(edges):
    answer = []

    graph = {}

    for edge in edges:
        u, v = edge[0], edge[1]

        if u not in graph:
            graph[u] = [v]
            continue
        graph[u].append(v)

    # find start point
    max_len_key = 999
    max_len = -99
    for k in graph:
        len_values = len(graph[k])
        if len_values >= max_len:
            max_len = len_values
            max_len_key = k

    print("max_len_key", max_len_key)

    # find donut count
    donut_count = 0
    donuts = set()

    # find direct count
    direct_count = 0
    directs = set()

    # find eight
    eight_count = 0
    eights = set()

    print("graph: ", graph)

    return answer

# O(1) = 1,000,000
# [a b] : a -> b 간선
# 최소 그래프 합은 2이상
# answer = [생성한 정점의 번호, 도넛 모양 그래프 수, 막대모양 그래프수, 8자 모양 그래프 수 ]