문제 설명

전체 코드

from collections import deque

def solution(n, vertex):
    def bfs(v):
        q = deque()
        q.append(v)
        visited[v] = 1
    
        while q:
            v = q.popleft()

            for i in matrix[v]:
                if visited[i] == 0:
                    dist[i] = dist[v] + 1
                    q.append(i)
                    visited[i] = 1

    matrix = [[] for _ in range(n+1)]
    visited = [0] * (n+1)
    dist = [0] * (n+1)

    for i in vertex:
        matrix[i[0]].append(i[1])
        matrix[i[1]].append(i[0])

    bfs(1)
    result = 0
    mx = max(dist)
    for i in dist:
        if i == mx:
            result += 1

    return result

해결 방법

가장 기본적인 그래프 문제이다. 이 문제는 dfs와 bfs로 풀 수 있지만 나는 bfs로 풀었다. 가장 핵심은 간선의 갯수를 세는 것이므로 dist라는 리스트를 하나 정의해서 정점 1부터 시작했을 때 부터 간선이 추가될 때마다 dist[연결된 정점] = dist[연결된 정점] + 1 을 해준다. 그 후에 max(dist) 값이 최대 간선이므로 이 값의 갯수를 세면 답이 된다.