[프로그래머스] LV3. 가장 먼 노드 - 파이썬

문제 링크

---

문제 요약

그래프 유형 에 해당한다.
단순하게 BFS를 활용해서 기준이 되는 "1" 노드와의 거리가 가장 먼 노드의 개수를 구한다.

---

문제 풀이

from collections import deque 

def solution(n, edge):
    answer = 0
    
    # 간선과 노드 정보 graph에 저장 
    graph= [[] for _ in range(n+1)]
    
    for e in edge:
        n1, n2 = e[0], e[1]
        graph[n1].append(n2)
        graph[n2].append(n1)
    #print(graph)
    
    # BFS 로직
    queue = deque([1])
    distance = [-1]*(n+1)
    distance[1] = 0 #출발 시작 노드 0 
    
    while queue:
        curr_node = queue.popleft()
        connect_edge = graph[curr_node]
        #print(connect_edge)
        for e in connect_edge:
            #print(f"{e} 입니다.")
            if distance[e] == -1: #방문한 적 없는 경우
                queue.append(e)
                distance[e] = distance[curr_node] + 1
    
    #print(distance) // [-1, 0, 1, 1, 2, 2, 2]
    
    max_dist = max(distance)
    
    for i in distance:
        if i == max_dist:
            answer +=1
    
    return answer

---

📌 느낀 점

• 삼성식 BFS/DFS 에 익숙해져 있는데 이렇게 간선/노드의 정보를 활용하는 문제에 익숙해지기 괜찮은 문제이다.