문제

[프로그래머스] 가장 먼 노드 (LV. 3)

요약

  • 1으로부터 가장 먼 노드의 개수를 반환하라

분류

  • 그래프
  • 자료구조

풀이

1. 내 풀이


  1. DFS 느낌
def solution(n, edge):
    arr = [[] for _ in range(n + 1)]
    visit = [True for _ in range(n)]
    for a, b in edge:
        arr[a].append(b)
        arr[b].append(a)
    queue = [1]

    while queue:
        t = []
        for q in queue:
            if visit[q - 1]:
                visit[q - 1] = False
                for v in arr[q]:
                    if visit[v - 1] and v not in t:
                        t.append(v)

        queue = t.copy()

        a = []
        for i, q in enumerate(queue):
            if visit[q - 1]:
                a.append(q)

        if len(a) == sum(visit):
            return len(a)