[Level 3] 프로그래머스 - 가장 먼 노드

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

풀이

• 노드 1번부터 출발하여 최단 거리로 이동할 떄
• 가장 멀리 있는 노드의 개수를 구하는 문제이다.
• 간선 수 기준이며, 모든 간선은 양방향이다.

모든 간선이 동일한 비용이기 때문에, BFS로 최단 거리를 구할 수 있다.

각 노드까지의 최소 간선 수를 구한 뒤, 가장 큰 거리 값을 갖는 노드의 개수를 세면 된다.

너무나도 자연스럽게 인접리스트는 무방향 그래프로 생성하고, 0-based index로 생성한다.

adj = [[] for _ in range(n)]
for u, v in edge:
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

BFS로 최단 거리를 계산해야하는데 다음과 같이 사용하였다.

dist = [-1] * n      # 거리 초기화 (-1은 방문 안함)
dist[0] = 0          # 시작 노드 거리 0
queue = deque([0])   # 시작 노드부터 BFS
 
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            queue.append(v)

BFS는 가까운 노드부터 차례로 방문하므로, 가장 먼저 방문한 거리가 최단 거리이다.

dist[i]는 1번 노드에서 i번 노드까지의 최소 거리가 저장된다.

max_dist = max(dist)
answer = dist.count(max_dist)

가장 큰 거리값을 갖는 노드의 개수를 센다.

코드

from collections import deque
 
def solution(n, edge):
    answer = 0
    adj = [[] for i in range(n)]
    
    for i in edge :
        u, v = i[0], i[1]
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    
    queue = deque()
    dist = [-1] * n
    queue.append(0)
    dist[0] = 0
    
    while queue :
        u = queue.popleft()
        for v in adj[u] :
            if dist[v] == -1 :
                dist[v] = dist[u] + 1
                queue.append(v)
    
    max_dist = max(dist)
    answer = dist.count(max_dist)
 
    return answer