[프로그래머스] 가장 먼 노드 by 파이썬(Python) : 그래프 bfs

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

난이도

LV 3

 

 

문제 설명

• n개의 노드가 주어지고 1번 노드로 부터 가장 먼 노드의 갯수를 구해서 Return 해주어야 한다.
• 이때 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 갯수가 가장 많은 노드를 의미한다.

 

접근법

• 그래프 이론 알고리즘의 인접 리스트 방식으로 주어진 입력을 변환해준다.
• 거리(간선 개수)를 저장 해줄 리스트를 만들고 BFS를 사용해 최단 경로의 간선 개수를 센후 저장해준다.
• count를 이용해 가장 큰 거리(간선개수)의 개수를 Return 해준다.

 

코드

from collections import deque
def solution(n, edge):
    answer = 0
    # 인접 리스트 만들기
    dic = {s:[] for s in range(1, n+1)}
    for s, e in edge:
        dic[s].append(e)
        dic[e].append(s)
        
    #거리 저장 List 
    distance = [-1]*(n+1)
    
    #bfs 구현
    q = deque([1])
    distance[1] = 0
    while q:
        n = q.popleft()
        for i in dic[n]:
            if distance[i] == -1: #해당노드가 방문하지 않은 노드이면 거리 갱신후 큐에 추가
                distance[i] = distance[n] + 1
                q.append(i)
    
    return distance.count(max(distance))

 

---

 

그래프 이론?

https://h-castle.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-Graph

[그래프 이론] 알고리즘 - 그래프 이론 (Graph)