[프로그래머스] Lv3. 가장 먼 노드

🔗

풀이

처음엔 현재 위치에서 다른 노드까지의 최단 거리를 너무 강조해서 다익스트라인줄 알았는데 일반 bfs로 풀면 되는 문제였다.

현재 위치에서 bfs로 탐색해서 가장 마지막에 탐색되는 위치의 개수를 구하면 된다. 일반적으로 visited에 현재까지 거린 거리를 저장해나가면서 탐색하고 마지막에 저장된 최대값의 개수를 카운트하면 된다.

여기서는 이동횟수를 기준으로 하여 각 단계별로 큐를 반복해서 가장 마지막에 구해지는 큐의 길이를 반환했다. 가장 마지막에 탐색된 큐 = 가장 멀리 있는 노드

def solution(n, edge):
    Q = [1]
    visited = [False]*(n+1)
    
    graph = [[] for _ in range(n+1)]
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    visited[1] = True
    while True:
        next_Q = []
        for now in Q:
            for next in graph[now]:
                if visited[next]:
                    continue
                    
                visited[next] = True
                next_Q.append(next)
    
        if not next_Q:
            return len(Q)
        
        Q = next_Q[:]

신선한(?) 풀이

큐에서 FIFO 방식으로 꺼내면서 푸는 일반적인 너비우선 탐색으로 구한 뒤 마지막에 최대값을 구하는 게 아니라 역정렬을 하고 가장 앞의 값을 구하는 방식. count에 시간이 많이 걸릴 거라고 생각했는데 생각보다 시간 차이는 많이 나지 않았다.

distances.sort(reverse=True)
answer = distances.count(distances[0])