[level 3] Title: 가장 먼 노드 파이썬

 

BFS를 활용하여 문제를 풀어보았다.

다른 문제를 풀 때, 거리가 필요하다면 거리정보를 담는 리스트를 따로 만들었을텐데, 이번에는 굳이 만들 필요가 없을 것이라고 생각했고, visited에 갱신된 적이 없을 경우, 1씩 더해가는 방법으로 답을 구했다.

 

from collections import deque
def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    # 방문 및 거리 갱신
    visited = [0] * (n+1)
    
    # 그래프 갱신
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    visited[1] = 1
    queue = deque([1])
    while queue:
        now = queue.popleft()
        for next in graph[now]:
            if not visited[next]:
                visited[next] = visited[now] + 1
                queue.append(next)
    
    target = max(visited)
    cnt = visited.count(target)
    
    return cnt

 

 

 

 

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