프로그래머스

프로그래머스 가장 먼 노드 풀이: 인접 리스트 BFS

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 가장 먼 노드
  • 출처: 프로그래머스 코딩테스트 연습, 그래프
  • 자체 판단 난이도: Level 3

간선이 가중치 없는 그래프에서 모든 노드까지의 최단 거리를 구해야 하므로 BFS와 인접 리스트를 함께 사용해야 한다. 방문 순서와 거리 상태를 정확히 관리해야 하므로 Level 3으로 판단했다.

1. 문제 요약

노드 번호가 1부터 n까지인 양방향 그래프에서 1번 노드로부터 최단 경로의 간선 수가 가장 큰 노드의 개수를 반환한다.

  • vertex[i] = [a, b]는 a와 b가 연결되어 있다는 뜻이다.
  • 그래프의 간선은 양방향이다.
  • n은 최대 20,000, 간선 수는 최대 50,000이므로 모든 경로를 반복해서 탐색하는 방식은 비효율적이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

각 노드에 연결된 노드를 빠르게 확인할 수 있도록 graph 인접 리스트를 만든다. 양방향 간선이므로 [a, b]를 입력받으면 a의 목록에 b, b의 목록에 a를 각각 추가한다.

dist[node]는 1번 노드에서 해당 노드까지의 최단 간선 거리다. 아직 방문하지 않은 노드는 -1로 두고, 시작 노드 dist[1]은 0으로 초기화한다.

BFS가 최단 거리를 보장하는 이유

모든 간선의 비용이 1이므로 BFS 큐에는 거리가 0인 노드, 1인 노드, 2인 노드 순으로 들어간다. 거리 d인 노드에서 처음 발견한 이웃은 반드시 거리 d + 1이다. 더 짧은 경로가 나중에 발견될 수 없으므로 처음 방문할 때의 거리를 최단 거리로 확정할 수 있다.

가장 먼 노드는 최단 거리의 최댓값으로 찾기

이 문제에서 “가장 멀다”는 단순히 탐색 과정에서 늦게 발견된다는 뜻이 아니라 1번에서의 최단 거리 값이 가장 크다는 뜻이다. 따라서 BFS가 끝난 뒤 dist[1:]에서 최댓값을 구하고, 그 값과 같은 원소를 세면 답이 된다.

그래프 불변식

큐에서 노드를 꺼낼 때마다 다음 조건이 유지된다.

  • 방문된 노드의 dist는 1번에서 그 노드까지의 최단 거리다.
  • 큐에는 아직 처리하지 않은 노드만 들어 있다.
  • 어떤 노드가 큐에 처음 들어가는 순간, 그 노드의 거리는 부모 노드의 거리보다 정확히 1 크다.

이 불변식은 방문 여부와 거리 기록을 하나의 배열로 관리할 때 유지된다. 이미 dist[next] != -1인 노드는 더 긴 우회 경로이므로 다시 큐에 넣지 않는다.

오답 접근과 반례

DFS에서 노드를 처음 방문했다는 사실만 기록하고 이후의 더 짧은 경로를 갱신하지 않으면 잘못된 거리를 확정할 수 있다. 다음 입력에서 인접 리스트의 순서대로 DFS가 1-2-4-5를 먼저 방문한다고 가정한다.

n = 5
vertex = [[1, 2], [1, 3], [2, 4], [4, 5], [3, 5]]

실제 최단 거리는 dist[4] = 2, dist[5] = 2이므로 정답은 2다. 하지만 방문한 노드를 다시 보지 않는 DFS는 5를 1-2-4-5 경로의 거리 3으로 먼저 기록할 수 있다. 이후 1-3-5의 거리 2를 확인하지 않으므로 최단 거리와 최댓거리 개수를 잘못 계산한다. DFS를 쓰려면 거리 갱신과 재방문 관리가 필요하며, 이 문제에서는 BFS가 더 직접적이다.

복잡도

각 노드와 간선을 BFS에서 한 번씩 확인하므로 시간 복잡도는 O(n + e)다. 인접 리스트, 거리 배열, 큐에 필요한 공간 복잡도도 O(n + e)다. 여기서 e는 간선 수다.

3. 문제 해결 코드 (Python)

from collections import deque


def solution(n, edge):
    graph = [[] for _ in range(n + 1)]

    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n + 1)
    dist[1] = 0
    queue = deque([1])

    while queue:
        node = queue.popleft()

        for next_node in graph[node]:
            if dist[next_node] != -1:
                continue

            dist[next_node] = dist[node] + 1
            queue.append(next_node)

    max_distance = max(dist[1:])
    return sum(distance == max_distance for distance in dist[1:])

dist[next_node] != -1이면 이미 더 짧거나 같은 거리로 방문한 노드이므로 건너뛴다. BFS가 끝나면 모든 노드의 최단 거리가 기록되어 있으므로 별도의 경로 복원 없이 최댓거리와 그 개수만 계산하면 된다.

공식 예제와 추가 검증

아래 케이스는 위 solution 함수를 실제로 실행해 결과를 확인했다.

공식 예제

입력: n = 6, edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
기대 출력: 3
확인 결과: 통과
검증 목적: 1번에서 최단 거리 2인 4, 5, 6을 함께 세는지 확인

추가 검증 1: 두 노드

입력: n = 2, edge = [[1, 2]]
기대 출력: 1
확인 결과: 통과
검증 목적: 최소 노드 수에서 유일한 이웃을 최댓거리 노드로 세는지 확인

추가 검증 2: 일렬 연결

입력: n = 4, edge = [[1, 2], [2, 3], [3, 4]]
기대 출력: 1
확인 결과: 통과
검증 목적: 최단 거리가 계속 증가하는 체인에서 마지막 노드 하나만 세는지 확인

추가 검증 3: 별 모양

입력: n = 5, edge = [[1, 2], [1, 3], [1, 4], [1, 5]]
기대 출력: 4
확인 결과: 통과
검증 목적: 같은 최단 거리 1을 가진 여러 노드를 모두 세는지 확인

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 최단 거리와 최댓거리 동률을 확인할 수 있다.

assert solution(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]) == 3
assert solution(5, [[1, 2], [1, 3], [1, 4], [1, 5]]) == 4

4. 다른 풀이 방식 검색 및 비교

참고 글도 거리 배열을 두고 BFS로 1번부터의 최단 거리를 계산한 뒤 최댓값의 개수를 센다. 이 글의 풀이 역시 같은 방향이지만, 방문하지 않은 상태를 -1로 명시하고 인접 리스트를 먼저 구성해 거리 확정 과정을 드러냈다. 간선 가중치가 없는 문제라 다익스트라보다 BFS가 적합하다.

마무리

가중치가 모두 같은 그래프에서는 BFS의 레벨이 곧 최단 간선 거리다. 인접 리스트와 거리 배열로 1번에서 모든 노드를 한 번씩 방문한 뒤 최댓거리의 개수를 세면 제한 조건 안에서 간단하고 안전하게 해결할 수 있다.

#그래프#프로그래머스#난이도 3