[BOJ/백준] 1167 - 트리의 지름 파이썬/Python3

BOJ 1167 - 트리의 지름 파이썬

---

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리의 지름 구하기 - 정형화된 문제 패턴 

1. 트리의 지름: 가장 먼 두 노드 사이의 거리

2. 선형 시간 안에 트리의 지름을 구하는 방법

 1) 트리에서 임의의 노드 X를 설정

 2) 노드 X를 기준으로 가장 먼 노드 Y를 탐색한다.

 3) 노드 Y를 기준으로 가장 먼 노드 Z를 탐색한다.

 4) 트리의 지름: 노드 Y와 노드 Z 사이의 거리

 

자세한 증명은 아래 블로그 참조

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

문제 풀이 코드

from collections import deque
import random

# 노드의 개수
n = int(input())
# 트리를 만들기 위해 - 리스트 활용
tree = [[] for _ in range(n + 1)]

# 정점 번호, 간선 정보 - 정점번호, 거리, 마지막 입력 -1
for _ in range(n):
    node = list(map(int, input().split()))
    # 0번째 idx는 정점번호, 1 ~ len(node)의 길이-2 idx (정점번호, 거리, 정점번호, 거리) 순으로 데이터가 저장, 마지막 idx: -1
    for i in range(1, len(node) - 2, 2):
        # 0번째 idx는 정점번호
        cur_edge = node[0]
        # 연결된 노드와 거리(정점번호, 거리)
        edge, cost = node[i], node[i + 1]
        tree[cur_edge].append((edge, cost))


def bfs(start):
    visit = [-1] * (n + 1)
    q = deque()
    q.append(start)
    visit[start] = 0
    # 거리가 가장 먼 트리의 지름과 정점을 저장하는 배열
    _max = [0, 0]

    while q:
        # 현재 기준 노드
        x = q.popleft()
        # 현재 기준 노드 x와 연결된 노드 중에서 거리가 가장 먼 노드를 찾는 과정
        for e, d in tree[x]:
            # 연결된 노드 중 아직 방문하지 않은 노드의 거리 갱신
            if visit[e] == -1:
                visit[e] = visit[x] + d
                q.append(e)
                # 현재 노드로부터 거리가 가장 먼 노드의 번호와 거리를 갱신
                if _max[0] < visit[e]:
                    _max = visit[e], e
    return _max


# 1) 트리에서 임의의 노드 X를 설정
random_node = random.randrange(1, n+1)
# 2) 노드 X를 기준으로 가장 먼 노드 Y를 탐색한다.
distance, node = bfs(random_node)
#  3) 노드 Y를 기준으로 가장 먼 노드 Z를 탐색한다.
distance, node = bfs(node)
# 4) 트리의 지름: 노드 Y와 노드 Z 사이의 거리
print(distance)

 

[참조블로그]

https://velog.io/@coding_egg/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1167번 : 트리의 지름 (python 파이썬)