문제

링크텍스트

난관

• 하나의 노드에 도달하는 경로가 여러개인 경우에 각각의 distance를 다 저장해야 하나 싶었다.
• 힌트를 보고 생각해 보니, 하나의 노드에서 출발하는 모든 경로를 다 검토 했다면, 그 노드는 큐에서 제거해도 되겠다는 결론을 얻었다.

결과

def solution(n, vertex):
    answer = 0
    graph =[[] for _ in range(n+1)]
    distance = [-1]*(n+1)
    for v in vertex:
        graph[v[0]].append(v[1])
        graph[v[1]].append(v[0])  
    s = [1]
    distance[1] = 0   
    while s:
        now = s[0]
        s = s[1:]
        for i in graph[now]:
            if distance[i] == -1 or distance[i] > distance[now] + 1:
                s.append(i)
                distance[i] = distance[now] + 1
    print(distance)
    for d in distance:
        if d == max(distance):
            answer += 1
    return answer