[그래프] 가장 먼 노드

어제 자기 전에 푼 가장 먼 노드라는 문제입니다.
문제는 시작점으로부터 가장 먼 노드의 개수를 구하는 문제입니다.
이 때 가장 먼 거리의 기준은 해당 노드까지 최단 거리로 움직였을 때 거리를 기준으로 합니다.
최단 거리란 말이 나왔으므로 BFS로 접근해야함을 직감합니다.

먼저 주어진 Node간 연결 데이터를 Defaultdict를 통해 graph화 시킵니다.

graph = defaultdict(list)
    
    # 그래프 작성
    for e1, e2 in edge:
        graph[e1].append(e2)
        graph[e2].append(e1)

그 다음, 시작점인 1번 노드를 기준으로 bfs를 수행합니다. 가장 먼 노드의 개수를 알아야 하기 때문에 노드를 방문할 때마다 거리를 기록해둡니다. 따로 배열을 만들지 않고 방문 처리를 하는 visited 배열의 값을 거리로 저장합니다. 1 이상이면 True로 인정되므로 방문 여부를 검사하는 역할까지 같이 수행이 가능합니다.

def bfs(n, start, graph):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    q = deque()
    q.append([start, 0])
    while q:
        cur, dist = q.popleft()
        for node in graph[cur]:
            if not visited[node]:
                q.append([node, dist+1])
                # 방문처리를 하면서 해당 노드까지의 거리를 기록
                visited[node] = dist+1
    return visited
                

이런식으로 받은 visited 배열에서 max값을 count하여 답으로 return해줍니다.

전체 코드는 다음과 같습니다.

from collections import defaultdict, deque

def bfs(n, start, graph):
    visited = [0 for _ in range(n+1)]
    visited[start] = 1
    q = deque()
    q.append([start, 0])
    while q:
        cur, dist = q.popleft()
        for node in graph[cur]:
            if not visited[node]:
                q.append([node, dist+1])
                # 방문처리를 하면서 해당 노드까지의 거리를 기록
                visited[node] = dist+1
    return visited
                
            

def solution(n, edge):
    answer = 0
    
    graph = defaultdict(list)
    
    # 그래프 작성
    for e1, e2 in edge:
        graph[e1].append(e2)
        graph[e2].append(e1)
        
    result = bfs(n, 1, graph)

    answer = result.count(max(result))
        
    return answer

전형적인 BFS 문제였습니다.

시간 복잡도 : O(V+E), V: 정점 간 간선의 개수, E: 정점의 개수
모든 정점을 한 번씩 방문하고, 그 때마다 그 정점의 모든 간선을 조사하므로 결과적으로 모든 간선도 방문하는 셈이다.