가장 먼 노드

문제설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

---

제한사항

 

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

---

입출력 예

---

입출력 예에 대한 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

풀이

BFS를 활용해 풀었다. queue를 굳이 import하지 않아도 리스트로 구현가능하다. 예를 들어, 리스트 q가 있다 하면 q.pop(0)을 하면 FIFO(선입선출)로 구현이 가능하다. 0은 0번째 index의 아이템을 삭제하라는 뜻이다.

문제의 예시에서 q에 담기는 순서를 고려해 묶음으로 나누어보면 1/2,3/4,5,6 이다. 1이 먼저 들어가고 1을 pop한 뒤에 2와 3이 들어간다. 중요한 점은 이 묶음을 단위로 distance가 1씩 증가한다는 것이다. 이를 구현하기 위해선 distance라는 리스트를 참조하면 된다. 예컨대 3은 1을 pop하면서 들어간 것이니 distance[0]보다 1만큼 큰 값을 distance[2]에 넣어주어야 한다.(리스트의 인덱스는 0부터 시작한다는 것을 유념하자)

def solution(n, edge):
    
    answer = 0
    arr = [[] for _ in range(n)]
    visit = [0 for _ in range(n)]
    distance = [0 for _ in range(n)]
    
    for path in edge:
        x = path[0]-1
        y = path[1]-1
        arr[x].append(y)
        arr[y].append(x)

    q = [0]
    visit[0] = 1
    
    while q:
        # pop(n)은 n번째 index를 리스트에서 삭제
        x = q.pop(0)
        for i in arr[x]:
            if visit[i] == 0:
                visit[i] = 1
                q.append(i)
                distance[i] = distance[x] + 1
                
    answer = distance.count(max(distance))
    
    
    return answer