[코딩테스트/프로그래머스/Python]가장 먼 노드

💡생각

그래프 문제가 감이 안잡히고 시간이 많이 지나 다른사람의 코드를 보기로 함.

⏬다른사람의 코드

위상정렬원리를 활용했다고 함.

🔗풀이 참고
https://moseory20.tistory.com/35

from collections import deque


def solution(n, edge):
    answer = 0
    route = [0]*(n+1) #노드 1부터 각 노드까지의 거리
    edge.sort() #노드 1부터 연결 정보 확인하기 위해 정렬
    queue = deque() 
    graph = [[] for i in range(n+1)] #각 노드에 연결된 노드 정보 저장
    
    for e in edge: # 양방향이므로 
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
    queue.append(1)
    route[1] = 1
    
    while queue:
        now = queue.popleft()
        for g in graph[now]:
            if route[g]==0:
                queue.append(g)
                route[g] = route[now]+1
        
    # 1번 노드로부터 가장 멀리 떨어진 노드 개수 계산
    max_edge= max(route)
    for r in route:
        if r == max_edge:
            answer+=1     
            
    return answer

✅위상 정렬

• 정렬 알고리즘의 일종.
• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다.
    2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
    2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
• 시간복잡도: O(V+E)

🔗프로그래머스 - 가장 먼 노드
https://programmers.co.kr/learn/courses/30/lessons/49189