[프로그래머스] 2024 KAKAO WINTER INTERSHIP | 도넛과 막대 그래프

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

일단 각 노드에서 들어가고 나오는 엣지의 개수를 세야한다고 생각했다.

그래서 edges_cnt를 이용해서 딕셔너리로 엣지 개수를 세주고 solution()에서 받아 저장했다.

근데 뭐 어ㅉㅓ라고 ? 그래프 구분을 어떻게 해야함 ?? 이라는 생각으로 하루를 보내버린 나자신..

엄청나게 친절한 프로그래머스 해설을 보고 수도코드마냥 코드를 작성했다...

코드를 짜는데는 문제가 없지만 그래프마다 특정 노드가 이러한 간선 특징을 가지고 있다는걸 알아채는게 어려운 문제였다.

0. 생성 정점 번호
   생성 정점은 들어오는 간선의 개수가 0, 나가는 간선의 개수가 2개 이상이다.

1. 막대 그래프(마지막 노드 기준)
   막대 그래프는 들어오는 간선의 개수가 1, 나가는 간선의 개수가 0이다.

2. 8자 그래프(가운데 중심이 되는 노드 기준)
   8자 그래프는 들어오는 간선의 개수가 2 이상, 나가는 간선의 개수도 2 이상이다.

3. 도넛 그래프
   도넛 그래프는 생성 정점에서 나가는 간선의 개수 - 막대 그래프 개수 - 8자 그래프 개수
   사실 이부분은 이해하기가 어렵긴 했다 ........

내가 풀었다고 하기도 뭐한 문제였다...

코드

---

def edges_cnt(edges):      
    cnt_edges = {}
    for a, b in edges:
        if not cnt_edges.get(a):
            cnt_edges[a] = [0, 0]
        if not cnt_edges.get(b):
            cnt_edges[b] = [0, 0]

        cnt_edges[a][0] += 1
        cnt_edges[b][1] += 1           

    return cnt_edges 

def solution(edges):
    answer = [0, 0, 0, 0]
    num_edges = edges_cnt(edges)

    for num_node, edges in num_edges.items():
        if edges[0] >= 2 and edges[1] == 0:
            answer[0] = num_node
        elif edges[0] == 0 and edges[1] >= 1:
            answer[2] += 1
        elif edges[0] >= 2 and edges[1] >= 2:
            answer[3] += 1

    answer[1] = num_edges[answer[0]][0] - answer[2] - answer[3]            

    return answer

결과

---