간선(edge) 리스트가 주어졌다고 가정해 보겠습니다. 각 항목 (u, v)는 u가 v의 부모 노드임을 나타냅니다. 이때 트리 전체에서 가장 긴 경로의 길이를 구해야 하며, 여기서 경로 길이는 1 + 해당 경로를 구성하는 노드의 개수로 정의합니다.
예를 들어 입력이 다음과 같다면
출력은 5가 됩니다. 가장 긴 경로가 [1, 4, 5, 7]이고 총 4개의 노드로 구성되어 있으므로, 경로 길이는 1 + 4 = 5이기 때문입니다.
해결 접근 방법
이 문제는 이중 BFS(Double BFS) 기법으로 효율적으로 해결할 수 있습니다. 임의의 노드에서 출발해 가장 먼 노드를 찾고, 그 노드에서 다시 한 번 BFS를 수행하면 트리의 지름, 즉 가장 긴 경로의 길이를 구할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 주어진 간선 리스트로부터 그래프의 인접 리스트(adjacency list) g를 생성합니다.
- 노드별 거리를 저장할 새로운 맵 d를 준비합니다.
- bfs() 함수를 정의합니다. 이 함수는 시작 노드 o를 인자로 받습니다.
- d[o] := 1로 초기화하고, f := o, 큐 q := [o]로 설정합니다.
- 큐의 각 노드 x에 대해 인접 노드 y를 순회하며, 아직 방문하지 않은 노드라면 d[y] := d[x] + 1로 거리를 갱신합니다.
- d[y] > d[f]인 경우 f := y로 갱신하여 현재까지 가장 먼 노드를 추적하고, y를 큐에 추가합니다.
- BFS가 끝나면 가장 먼 노드 f를 반환합니다.
- 메인 로직에서는 임의의 시작 노드 o에 대해 첫 번째 bfs(o)를 호출해 가장 먼 노드 f를 찾습니다.
- 거리 맵 d를 초기화한 뒤 f에서 두 번째 bfs(f)를 수행하고, 그 결과 노드까지의 거리 d[bfs(f)]를 반환합니다. 이 값이 곧 가장 긴 경로의 길이입니다.
- 그래프가 비어 있는 경우에는 0을 반환합니다.
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(edges):
g = {}
for u, v in edges:
if u not in g:
g[u] = []
g[u] += (v,)
if v not in g:
g[v] = []
g[v] += (u,)
d = {}
def bfs(o):
d[o] = 1
f = o
q = [o]
for x in q:
for y in g[x]:
if y not in d:
d[y] = d[x] + 1
if d[y] > d[f]:
f = y
q += (y,)
return f
for o in g:
f = bfs(o)
d = {}
return d[bfs(f)]
return 0
edges = [(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]
print(solve(edges))
입력
[(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]
출력
5