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

programmers.co.kr/learn/courses/30/lessons/49189

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

백준에서 많이 풀어본 그래프 문제들과 비슷하다.

처음에 DFS로 풀어보려다 실패하고 BFS로 풀었다.

 

from collections import deque
def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    dist = [0] * (n+1)
    visited = [False] * (n+1)
    q = deque()
    q.append(1)
    visited[1] = True
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    while q:
        x = q.popleft()
        for i in graph[x]:
            if not visited[i]:
                dist[i] = dist[x] + 1
                q.append(i)
                visited[i] = True

    return dist.count(max(dist))

 

프로그래머스는 BOJ와 제출하는 코드형식이 약간 달라 (프로그래머스는 solution이라는 함수에 매개변수를 다 넣어주고 solution 함수를 작성한 뒤 답을 return 하는 형식이다.) 처음 이용하는 사람들은 출력처리를 하는 데 시간이 걸릴 수도 있다.

나도 처음엔 익숙하지 않아서 적응하는데 시간이 조금 걸렸다.