[solved.ac 골드2] 1167_트리의 지름 (파이썬, BFS)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제

---

나의 풀이

이 문제가 골드2 인 것은 절대 어려운 알고리즘이나 복잡한 구현 때문이 아니라 문제를 풀 아이디어를 떠올리기 어려운 이유라는 생각이 든다.

아이디어만 알게 되면 실제 구현 난이도는 실버1 정도 되지 않을까 생각한다.

 

아이디어

문제를 푼 이후에 질문 게시판에 들어가봤는데 아주 좋은 비유가 있어 잠시 빌려와 설명해보려고 한다.

위 그림은 문제의 예제를 트리로 그린 것이다. 주황색 숫자는 간선의 길이를 의미한다.

 

이제 트리에서 각 노드를 구슬로 생각하고, 간선을 구슬을 연결하는 실로 생각해보자.

이 문제에서 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다고 했다.

구슬과 실로 생각했을 때 구슬을 한 손에 하나씩 잡고 길게 쭉 잡아 당긴 길이가 가장 긴 것을 찾는 걸로 생각할 수 있다.

 

어떻게 찾아야 할까? 상상력을 발휘해보자.

 

임의의 구슬을 하나 잡고 길게 쭉 늘어뜨리면 다음과 같이 될 것이다.

2번 구슬을 잡고 늘어뜨린 모습

이때 가장 밑에까지 내려오는 구슬이 있을텐데 이 구슬이 가장 긴 두 구슬 중 하나일 것이다.

둘 중 하나를 찾았으니 나머지 하나를 찾는 것은 쉽다.

 

위에서 찾았던 5번 구슬을 잡고 늘어뜨리면 가장 긴 길이를 찾을 수 있다.

트리의 지름을 찾는 것이다.

 

정리하자면

1. 임의의 노드를 선택해서 가장 거리가 먼 노드의 인덱스를 찾는다
2. 1번에서 찾은 인덱스로 다시 탐색을 해서 가장 거리가 먼 노드를 찾는다
3. 1, 2번에서 찾는 노드 사이의 길이를 구한다

 

전체 코드

from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

n = int(input())
li = [[] for _ in range(n + 1)]

for _ in range(n):
    info = list(map(int, input().split()))
    for i in range(1, len(info) - 1, 2):
        li[info[0]].append((info[i], info[i + 1]))

def bfs(x):
    distance = [0] * (n + 1)
    visited = [False] * (n + 1)
    q = deque([(x, 0)])
    visited[x] = True

    while q:
        now, dist = q.popleft()
        for nxt, d in li[now]:
            if visited[nxt]: continue
            distance[nxt] = dist + d
            visited[nxt] = True
            q.append((nxt, distance[nxt]))

    return distance

for i in range(1, n + 1):
    if li[i]:
        distance = bfs(i)
        break

max_index = max(zip(distance, range(n + 1)))[1]
result = bfs(max_index)

answer = 0
for i, r in enumerate(result):
    if i != max_index and answer < r:
        answer = r

print(answer)

채점 결과