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

문제

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

프로그래머스

 

 

 

---

 

주요 아이디어

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하는 문제이다.

• BFS를 통해 인접 노드를 탐색
• distance 배열을 통해서 노드 1과의 거리가 얼마인지를 저장
  • 이 때 시작점은 1번 노드 고정이므로 1차원 배열로 커버 가능하다

 

---

 

코드 구현 (Python 3)

 

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    distance = [0] * (n+1)
    
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    
    for idx in range(len(graph)):
        graph[idx].sort()
    
    # 초기값 설정
    queue = deque();
    queue.append(1)
    distance[1] = 1
        
    while queue:
        cur = queue.popleft()
            
        for adj in graph[cur]:
            if distance[adj] == 0:
                queue.append(adj)
                distance[adj] = distance[cur] + 1
            
    
        
    return len([x for x in distance if x == max(distance)])

 

 

---

제출 결과