프로그래머스 등급3 - 가장 먼 노드

가장 먼 노드 문제 바로 가기

풀이 날짜: 2026-05-07

baekjoon 알고리즘 문제 풀이

풀이 코드


from collections import deque

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n+1)]
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    distance = [-1] * (n+1)
    
    def bfs(start):
        q = deque()
        q.append(start)
        distance[start] = 0
        
        while q:
            x = q.popleft()
            for next in graph[x]:
                if distance[next] == -1:
                    distance[next] = distance[x] + 1
                    q.append(next)
    
    bfs(1)
                    
    max_distance = max(distance)
    return distance.count(max_distance)

문제 핵심

처음에는 모든 노드 사이의 거리를 저장하기 위해 2차원 거리 배열을 만들려고 했다. 하지만 이 문제에서 필요한 것은 모든 노드 간의 최단거리가 아니라, 1번 노드에서 각 노드까지의 최단거리였다. 따라서 2차원 배열이 아니라 1차원 distance 배열만 사용하면 충분했다. 문제의 목표는 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 구하는 것이므로, BFS를 통해 각 노드까지의 거리를 계산하는 방식으로 접근했다.

그래프 구성

입력으로 주어지는 edge는 노드 사이의 연결 정보를 담고 있다. 이 문제의 간선은 방향이 없는 양방향 연결이기 때문에, [a, b]가 주어지면 a → b뿐만 아니라 b → a도 함께 저장해야 한다. 그래서 인접 리스트 형태의 그래프를 만들고, 각 노드에서 이동할 수 있는 노드를 리스트에 추가했다.

BFS를 선택한 이유

이 문제는 간선의 가중치가 모두 같은 그래프에서 최단거리를 구하는 문제이다. 이런 경우에는 다익스트라보다 BFS가 더 적합하다. BFS는 시작 노드에서 가까운 노드부터 차례대로 방문하기 때문에, 어떤 노드를 처음 방문했을 때의 거리가 곧 최단거리가 된다. 따라서 1번 노드에서 시작해 BFS를 수행하면 모든 노드까지의 최단거리를 자연스럽게 구할 수 있다.

거리 배열 사용

방문 여부와 거리를 동시에 관리하기 위해 distance 배열을 사용했다. 처음에는 모든 값을 -1로 초기화하여 아직 방문하지 않은 상태를 표시했다. 이후 1번 노드에서 BFS를 시작하므로 distance[1] = 0으로 설정했다. 여기서 0은 1번 노드에서 자기 자신까지의 거리가 0이라는 의미이다. 그리고 BFS 중 아직 방문하지 않은 노드를 만나면 현재 노드의 거리보다 1 큰 값으로 갱신했다.

가장 먼 노드 찾기

BFS가 끝난 뒤에는 distance 배열에서 가장 큰 값을 찾으면 된다. 이 값이 1번 노드에서 가장 멀리 떨어진 거리이다. 이후 그 거리와 같은 값을 가진 노드의 개수를 세면 정답이 된다.

구현하면서 헷갈렸던 점

처음에는 2차원 거리 배열을 만들고 자기 자신은 0, 연결된 곳은 1로 저장하려고 했다. 하지만 이 방식은 모든 노드 사이의 거리를 구하는 플로이드 워셜 방식에 가까웠고, 이 문제에서는 필요하지 않았다. 또한 BFS 함수를 정의한 뒤 실제로 bfs(1)을 호출하지 않으면 거리 배열이 갱신되지 않는다. 마지막으로 q,append(next)처럼 쉼표를 잘못 사용한 오타도 있었는데, 올바른 코드는 q.append(next)이다.

Vienna sausage