[PG/Python] 가장 먼 노드

📌 문제

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

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

 

📌 문제 접근 방법

1. 인접 리스트를 활용해서 그래프 정보를 저장해준 뒤 bfs를 사용했다.
2. bfs에서 방문체크를 할 때, 1번 노드와의 거리를 저장해줬다.
   (가장 먼 거리가 1일 경우에도 1번 노드는 포함되지 않아야하므로 1번 노드는 -1로 방문체크를 해줬다.)
3. bfs 탐색이 끝난 후, visited를 순회하면서 거리가 가장 먼 노드의 개수를 세어 반환한다.

 

📌 코드

from collections import deque

def bfs(n, graph):
    queue = deque()
    queue.append((1, 0))
    
    visited = [0 for _ in range(n+1)]
    visited[1] = -1
    
    while queue:
        v, dist = queue.popleft()
        
        for w in graph[v]:
            if not visited[w]:
                visited[w] = dist+1
                queue.append((w, dist+1))
    
    cnt = 0
    for dist in visited:
        if dist == max(visited):
            cnt += 1
    
    return cnt


def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    
    for n1, n2 in edge:
        graph[n1].append(n2)
        graph[n2].append(n1)
    
    answer = bfs(n, graph)
    return answer