[프로그래머스] Level3, 가장 먼 노드 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3 

코딩테스트 연습 - 가장 먼 노드

 

코드

import collections
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [False for _ in range(n+1)]
    distance = [0 for i in range(n+1)]
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
        
    queue = collections.deque()
    queue.append(1)
    def bfs():
        while queue:
            cur = queue.popleft()
            visited[cur] = True
            for next in graph[cur]:
                if visited[next] == False:
                    visited[next] = True
                    distance[next] = distance[cur] + 1
                    queue.append(next)
    bfs()
    maxx = max(distance)
    for i in distance:
        if maxx == i:
            answer += 1
    return answer

경로에 거리를 구하는 문제로 bfs를 사용하여 풀어줬다.

 

edge를 받아 for문을 돌아 graph에 인접리스트 형식으로 넣어주고 bfs를 수행한다.

 

1노드 부터 bfs를 돌아 distance에 각노드와의 거리가 저장이 되고 for문을 돌아 가장 큰값에 갯수를 세어 반환한다.