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

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

2024 KAKAO WINTER INTERNSHIP

카카오 문제 새로 올라와서 풀어보았다.

 

정점의 번호를 찾는 방법과

그래프들의 규칙을 찾는 게 중요하다고 생각했다.

 

정점의 번호(4)를 보면

간선이 나가는거 밖에 없다.

나가는 간선이 제일 많은 노드가 정점의 번호이다.

4번 노드 보면 나가는 간선이 제일 많다. 얘가 정점 노드이다.

그리고 4번 노드에 연결된 노드 [8,2,11]이 어떤 그래프들의 시작점으로 활용한다.

[8,2,11]을 하나씩 탐색하여 그래프의 종류를 파악해야 한다.

 

그래프들의 특성을 파악해 본다.

먼저 8자 그래프를 확인해 본다.

8자 그래프의 특징은 나가는 간선이 2개가 있는 경우가 있다.

해당 위의 그림을 보면 [3,11]이 해당사항이다.

 

막대 모양 그래프는 탐색 도중 길이 끊긴다

끊긴 시점에 count를 증가시킨다.

 

도넛그래프는

탐색을 진행하면 무한루프가 생긴다.

그래서 시작지점을 기준으로 한 바퀴 돌고 나서 검사를 한다.

8자 그래프, 막대 모양 그래프에 해당되지 않았을 경우에는 도넛 그래프이다.

 

 

from collections import defaultdict, deque
def solution(edges):
    answer = [0,0,0,0]
    indegree = defaultdict(int)
    graph = defaultdict(list)

    for i in edges:
        indegree[i[0]] += 1
        graph[i[0]].append(i[1])
    root_node = max(indegree, key=indegree.get)
    answer[0] = root_node
    for sub_node in graph[root_node]:
        queue = deque([sub_node])
        donut = defaultdict(int)
        while queue:
            pop_node = queue.popleft()
            donut[pop_node] += 1
            if len(graph[pop_node]) > 1:
                answer[3] += 1
                break
            if graph[pop_node] == []:
                answer[2] += 1
                break
            if donut[sub_node] == 3:
                answer[1] += 1
                break

            queue.append(graph[pop_node][0])
    return answer