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

lv. 3 단계의 코딩 테스트 연습 문제 중 '가장 먼 노드'에 대한 풀이를 설명하고 있습니다.

 

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

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 이 문제는 우선 순위 큐를 가지고 BFS를 돌리면 정말 금방 끝난다.
• 다익스트라와 같이 이전에 탐색된 노드들의 거리를 갱신해줄 필요가 없는 이유는 간선의 거리가 모두 1로 통일이기 때문에 노드를 많이 거쳐가면 무조건 오래 걸린다.
• 예를 들어, 다익스트라에서는 1->2로 이동하는데는 5가 걸리는데, 1->3->2로 가면 3이 걸릴 수 있다.
• 따라서 특정 점에서 특정 점까지의 거리를 계속해서 갱신해야 한다.
• 하지만, 현재 상황에서는 1->2가 1->3->2보다 무조건 빠르다는 것을 알고 있다.
• 따라서, 우선 순위 큐를 가지고 1에서 가까운 점들부터 탐색하는 식으로 다음 노드를 꺼낸다면 쉽게 끝나는 것이다.
• 결론적으로, 방문한 노드는 다시 방문할 필요가 없고, BFS와 같이 해당 점에 먼저 도착한 경로가 곧 최단 경로라는 것을 명심하면 된다.
• 코드는 아래와 같다.

코드

import heapq
from collections import deque, defaultdict
def solution(n, edge):
    answer = 0
    
    graph = defaultdict(list)
    for (x, y) in edge:
        graph[x].append(y)
        graph[y].append(x)
        
    q = []
    distance = [20001 for _ in range(n + 1)]
    heapq.heappush(q, [0, 1])
    
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] != 20001:
            continue
        distance[node] = dist
        for i in graph[node]:
            heapq.heappush(q, [dist+1, i])
    maxDist = max(distance[1:])
    answer = distance.count(maxDist)
    return answer

 

백준 골드 3이 코앞이다. 조금만 더 열심히 하면 될 것 같다. 이번주 현대퓨처넷 코테도 아자아자 화이팅!

 

추천글

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

프로그래머스