[프로그래머스] 49189 가장 먼 노드

이강혁·2024년 8월 14일
0

프로그래머스

목록 보기
65/79
post-custom-banner

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

그래프에서 1번 노드에서 최단 경로로 갔을 때 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.

from collections import defaultdict

def solution(n, edge):
    answer = 0
    graph = defaultdict(list)
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    que = []
    idx = 0
    que.append((1, 0))
    visited = [True] * (n+1)
    visited[1] = False
    while idx < len(que):
        now, count = que[idx]
        idx += 1
        
        for next in graph[now]:
            if visited[next]:
                visited[next] = False
                que.append((next, count+1))
                
    max = que[-1][1]
    
    for idx, length in que:
        if max == length:
            answer+=1
    
    return answer

BFS를 활용해서 탐색을 하는데 1번 노드의 거리는 0으로 시작해서 주변에 연결된 노드를 찾아갈 때 현재 거리에 1을 더해주었다.
가장 마지막에 추가된 노드가 가장 멀 것이라고 판단하였고 해당 거리를 기준으로 나머지 노드와 거리를 비교해서 가장 먼 곳에 있는 노드들의 개수를 구했다.

profile
사용자불량
post-custom-banner

0개의 댓글