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

사용 언어 - Python3

문제 -  가장 먼 노드

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

프로그래머스

 

 

정답

구현

연결된 노드를 모두 확인해주면서 max(거리)인 경우를 카운트하기

1. 연결된 노드 정보를 저장해준다.

예) graph[1번노드] = 3번 노드 , grpah[3번 노드] = 1번 노드

 

2. 각 노드를 기준으로 최단거리를 저장할 distance 리스트를 생성한다.

거리는 0 일수도 있으니 디폴트값을 -1로 설정한다.

distance = [-1] * (n+1)

 

3. 1번노드에서 출발

queue = deque([1])

distance[1] = 0

최단거리는 0으로 설정해준다.

 

4. BFS 수행

현재 노드 now 에서 이동할 수 있는 모든 노드를 방문한다.

방문하지 않았던 노드 즉, distance가 디폴트값인 -1인 경우만 방문하면서

최단거리를 갱신한다. distance[i] = 현재까지의 distance + 1

 

5. 가장 멀리 떨어진 노드 개수를 구한다.

distance 들 중에 max(distance)인 경우 answer += 1 

 

from collections import deque
def solution(n, edge):
    answer = 0
    
    # 연결된 노드 정보 그래프
    graph = [[] for _ in range(n+1)]
    
    # 각 노드의 최단거리 리스트. 거리는 0일수도 있으니 -1을 디폴트값으로 설정
    distance = [-1] * (n+1)
    
    # 연결된 노드 정보 추가. 양방향 연결
    for e in edge :
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    
    # BFS를 위한 queue, 출발 노드 = 1
    queue = deque([1])
    
    # 출발노드의 최단거리를 0으로
    distance[1] = 0 
    
    # BFS 수행
    while queue :
        now = queue.popleft() # 현재 노드
        # 현재 노드에서 이동할 수 있는 모든 노드 확인
        for i in graph[now]:
            if distance[i] == -1: # 아직 방문하지 않은 노드인 경우
                queue.append(i) # queue에 추가
                distance[i] = distance[now] + 1 # 최단거리 갱신
    
    # 가장 멀리 떨어진 노드 개수 구하기
    for d in distance:
        if d == max(distance):
            answer += 1
    
    return answer

 

 

레퍼런스

• 깃허브 정답