[프로그래머스] 도넛과 막대 그래프

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258711

2024 카카오 겨울 인턴쉽 문제이다.

프로그래머스

문제 요약 : 그래프의 종류가 도넛, 막대, 8자로 총 3가지가 있다. 각 그래프의 노드 숫자와 간선의 숫자가 다르다는 특징이 있다.

서로 다른 종류의 그래프들이 주어지고 임의의 노드가 이 그래프들의 중간에 위치하여 모든 노드가 이어진다.

이 때, 임의의 노드가 몇 번이 찾고 각 그래프들의 종류는 몇 개인지를 반환하는 문제이다.

 

문제 풀이

1. 임의의 노드는 각 그래프들을 이어주는 것이기 때문에 inbound(들어오는 간선)가 0이다. 그리고 inbound가 0인 노드들 중에서는 outbound(나가는 간선)이 가장 크다. 왜냐하면 도넛, 막대, 8자 그래프의 특징에 따라서 inbound가 0이면 outbound는 0이기 때문이다.

2. 임의의 노드로부터 시작되는 정점(임의의 노드의 outbound)들이 각 나누어진 그래프들의 종류이다. 따라서 각 그래프들을 순회하면서 정점 수와 간선 수를 비교하며 도넛, 막대, 8자 그래프를 구분한다.

 

해답 코드

from collections import deque

def solution(edges):
    answer = []
    maxv = -float('inf')
    for i, j in edges:
        if i > j:
            if maxv < i:
                maxv = i
        else:
            if maxv < j:
                maxv = j
                
    # 1번
    center = []
    for i in range(maxv):
        center.append([0, 0])
    
    for i, j in edges:
        center[i-1][1] += 1
        center[j-1][0] += 1
    
    node = 0
    nodev = 0
    for i in range(len(center)):
        if center[i][0] != 0:
            continue
        if center[i][1] > nodev:
            nodev = center[i][1]
            node = i
    node += 1
    answer.append(node)
    
    # 2번
    donut = 0
    stick = 0
    eight = 0

    graph = [[] for _ in range(maxv)]
    startv = [] # 임의의 노드에서 시작되는 노드들을 담는 리스트
    for start, end in edges:
        if end == node:
            continue
        elif start == node:
            startv.append(end-1)
            continue
        graph[start-1].append(end-1)
        
    def bfs(start_v):
        visited = set() # set이 아닌 배열로 방문 여부를 판단하면 시간초과가 발생한다.
        node = 0
        edge = 0
        stack = deque([start_v])
        while stack:
            v = stack.popleft()
            if v not in visited:
                visited.add(v)
                node += 1
                for w in graph[v]:
                    stack.append(w)
                    edge += 1
                    
        return node, edge
    
    temp = []
    for i in startv:
        temp.append(bfs(i))
        
    for node, edge in temp:
        if node-1 == edge:
            stick += 1
        elif node == edge:
            donut += 1
        else:
            eight += 1
            
    answer.append(donut)
    answer.append(stick)
    answer.append(eight)
    
    return answer

 

여기서 눈여겨 봐야할 점은 각 그래프들의 노드와 간선 수를 구하는 bfs 함수에서 set 자료구조인 visited이다.

set 대신에 리스트를 사용하여 visited = []와 같이 작성하면 시간초과가 발생한다.

visited가 리스트인 경우, if v not in visited 구문은 리스트의 각 요소에 대해 순차적으로 검색을 수행하게 된다.

따라서 이는 최악의 경우 O(n)의 시간 복잡도를 가지기 때문에 비효율적입니다.
반면에 set은 해시 테이블을 사용하여 O(1)의 시간 복잡도를 가지며 요소에 대한 검색을 빠르게 수행한다.

따라서 BFS나 DFS와 같이 반복적으로 노드를 검색하고 방문 여부를 확인하는 경우, 집합(set)을 사용하는 것이 일반적으로 효율적이다.