[python] 프로그래머스 - 가장 먼 노드

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

# n개의 노드가 있는 그래프에서각 노드는 1~n으로 주어짐
# 가장 멀리 떨어진 노드란 최단경로로 이동 했을 때 간선의 개수가 가장 많은 노드

# 1번 노드로부터 가장 멀리 떨어진 노드의 개수

 

 

먼저, 생각해야 할 부분

 

1. 1번 노드로부터의 최단 경로를 찾고 있다

     -> 다익스트라 알고리즘

2. BFS를 이용한 풀이 역시 가능하다.

---

 

다익스트라를 이용한 풀이

 

from heapq import heappush, heappop
from collections import Counter, defaultdict

def solution(n, edge):
    INF = float('inf')
    
    answer = 0

    ad_list = defaultdict(lambda : [])
    
    # 그래프 초기화
    for v1, v2 in edge:
        ad_list[v1 - 1].append(v2 - 1)
        ad_list[v2 - 1].append(v1 - 1)
        
    # 다익스트라
    # 최소 거리를 갱신하는 것
    min_dis = [INF for _ in range(n)]
    heap = []
    visited_set = set()
    
    # 다익 초기화
    min_dis[0] = 0
    heappush(heap, (0, 0))
    
    while len(heap) > 0:
        current_dis, current_node_idx = heappop(heap)
        
        # 방문했다면 패스
        if current_node_idx in visited_set:
            continue
            
        visited_set.add(current_node_idx)
        
        # 인접 노드 최소 거리 갱신
        for near_node in ad_list[current_node_idx]:
            min_dis[near_node] = min(min_dis[near_node], current_dis + 1)
            
            # 힙에 넣자.
            heappush(heap, (min_dis[near_node], near_node))

    return Counter(min_dis)[max(min_dis)]

 

BFS를 이용한 풀이

 

from collections import deque, defaultdict, Counter

def solution(n, edge):
    INF = float('inf')
    
    answer = 0
    
    ad_list = defaultdict(lambda : [])
    
    # 그래프 초기화
    for v1, v2 in edge:
        ad_list[v1 - 1].append(v2 - 1)
        ad_list[v2 - 1].append(v1 - 1)
        
    # BFS
    min_dis = [INF for _ in range(n)]
    queue = deque()
    visited_set = set()
    
    # BFS 초기화
    min_dis[0] = 0
    queue.append(0)
    visited_set.add(0)
    
    while len(queue) > 0:
        current_node = queue.popleft()
        
        # 방문한 적이 없는 인접노드에 대해서
        for near_node in ad_list[current_node]:
            if near_node not in visited_set:
                # 최단 거리 갱신 (방문한 적 없는 노드만 queue에 들어가므로, 방문한 순간이 최단 거리)
                min_dis[near_node] = min_dis[current_node] + 1
                # 큐에 들어가기 전에 방문 체크
                visited_set.add(near_node)
                # 큐에 넣음
                queue.append(near_node)

    return Counter(min_dis)[max(min_dis)]

---

시간 복잡도

다익스트라 : O(edge * log n)

BFS : O(edge * n) / 추측

 

 

알게 된 점

 

인접 행렬을 이용할 경우 시간초과가 날 수 있음

 

인접 리스트는 연결된 노드를 바로 가져오지만,

인접 행렬은 행 전체를 탐색하면서 연결된 노드를 찾아내야함.

때문에 불필요한 조회가 늘어나 시간을 소모하게 됨.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들