[프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP) - Python

문제

도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)

아이디어

1. 먼저 루트 노드를 알아내야 한다.
   루트 노드는 특징이 있는데,
   들어오는 간선은 없으면서 나가는 간선이 2개 이상(그래프가 2개 이상 존재한다는 문제 조건 때문)이라는 것이다.

   edges를 탐색하며 딕셔너리 out에 나가는 간선 수를 저장했다. 이 때, 들어오는 간선이 있는 노드는 딕셔너리에서 삭제하여 루트 노드 후보군을 추렸다.

    answer = [0, 0, 0, 0]    
    adj = defaultdict(list)
    out = defaultdict(int)
    for a, b in edges:
        adj[a].append(b)
        out[a] += 1
        if b in out:
            del out[b]
    for node, cnt in out.items():
        if cnt >= 2:
            answer[0] = node
            break
   

   
   

2. 루트 노드의 인접 노드들 각각을 기점으로, bfs 탐색을 하여 그래프의 종류를 판별한다.

   bfs 탐색 로직에서 고민을 많이 했는데
   도넛이나 8자 그래프는 동일한 노드를 두 번 방문 할 수 있기 때문에, 노드를 기준으로 방문 여부를 체크하고 큐에 넣으면 카운트하지 못하는 간선이 존재할 수 있다는 것이다.

   그래서 방문한 간선과 노드를 모두 체크하도록 visited를 set으로 두었다.

   이를 통해 현재 노드 cur의 인접 노드들을 탐색할 때,

   • (cur, nxt) 간선을 방문한 적 없는가?

     간선 수 1 증가 e += 1
     간선 방문 체크
     큐에 nxt 노드 추가

     • nxt 노드도 방문한 적이 없는가?

       노드 수 1 증가 v += 1
       노드 방문 체크

    visited = set()
    dq = deque([srt])
    visited.add(srt)
    v, e = 1, 0
    while dq:
        cur = dq.popleft()
        for nxt in adj[cur]:
            if (cur, nxt) not in visited:
                e += 1
                visited.add((cur, nxt))
                if nxt not in visited:
                    v += 1
                    visited.add(nxt)
                dq.append(nxt)
   

   bfs 탐색을 마친 후, 노드 수 v와 간선 수 e를 통해 그래프 종류를 판별해준다.

    if v+1 == e:
        answer[3] += 1
    elif v-1 == e:
        answer[2] += 1
    elif v == e:
        answer[1] += 1
   

   
   

전체 코드

from collections import defaultdict, deque

def solution(edges):
    answer = [0, 0, 0, 0]    
    adj = defaultdict(list)
    out = defaultdict(int)
    for a, b in edges:
        adj[a].append(b)
        out[a] += 1
        if b in out:
            del out[b]
    for node, cnt in out.items():
        if cnt >= 2:
            answer[0] = node
            break
    
    for srt in adj[answer[0]]:
        visited = set()
        dq = deque([srt])
        visited.add(srt)
        v, e = 1, 0
        while dq:
            cur = dq.popleft()
            for nxt in adj[cur]:
                if (cur, nxt) not in visited:
                    e += 1
                    visited.add((cur, nxt))
                    if nxt not in visited:
                        v += 1
                        visited.add(nxt)
                    dq.append(nxt)
        if v+1 == e:
            answer[3] += 1
        elif v-1 == e:
            answer[2] += 1
        elif v == e:
            answer[1] += 1
    return answer