[PG_49189/Python] 가장 먼 노드

문제

49189번: 가장 먼 노드

코딩테스트 연습 - 가장 먼 노드

 

---

맞은 풀이

from collections import deque


def bfs(graph, n):
    q = deque()
    q.append((1, 0))  # 시작노드, 거리

    visited = [-1 for x in range(n + 1)]
    visited[1] = 0
    
    while q:
        x, d = q.popleft()
        
        for i in graph[x]:
            if visited[i] == -1:
                visited[i] = d + 1
                q.append((i, d + 1))
    
    max_val = max(visited)
    return visited.count(max_val)
    
    
def solution(n, edge):
    # 1. 인접그래프 만들기
    graph = [[] for _ in range(n + 1)]
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    
    for e in graph:
        e.sort()
        
    # 2. 거리 구하기
    return bfs(graph, n)

BFS를 이용해서 노드 사이의 최단 거리를 구했다. visited 배열이 방문 체크를 함과 동시에 노드 1부터의 거리를 가진다. visited 배열의 최댓값의 개수를 세면 가장 먼 노드의 개수를 구할 수 있다.