[programmers/py] 가장 먼 노드

가장 먼 노드

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

문제 설명

1부터 N까지 번호가 적힌 노드와 그래프가 있습니다.
1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.
가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

주어진 항공권은 모두 사용해야 합니다.

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

풀이 설명

BFS 문제
1. graph배열에 각 노드의 이동 가능한 경우를 넣는다.
2. bfs를 통해 각 높이마다 dict[높이]에 노드를 추가

굳이 노드를 추가할 필요 없이 노드의 수를 구하면 되는 문제라 +1을 해도 됨

dfrom collections import deque

def solution(n, edge):    
    graph = [[] for _ in range(n+1)]
    visited = [False]*(n+1)
    
    dic = {}
        
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    def bfs(start, d):
        m = 0
        visited[start] = True
        dq = deque()
        dq.append([start, d])
        
        while dq:
            now, dist = dq.popleft()
            
            if dist > m:
                m = dist
            
            if dist+1 not in dic:
                dic[dist+1] = []

            for i in graph[now]:
                if not visited[i]:
                    visited[i] = True
                    dic[dist+1].append(i)
                    dq.append([i, dist+1])
        return m
    
    m = bfs(1,1)
    return len(dic[m])