[BOJ] 1167 / 트리의 지름 / Python 파이썬

[BOJ] 1167 / 트리의 지름 / Python 파이썬

[BOJ] 1167 / 트리의 지름 / Python 파이썬

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

1167번: 트리의 지름

 

풀이

Tree 의 지름을 구하는 문제이다.

 

문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다.

 

 

• Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로

 

• 선형 시간내에 Tree 의 지름을 구하는 Algorithm

1. 트리에서 임의의 정점 xx를 잡는다. 
2. 정점 xx에서 가장 먼 정점 yy를 찾는다
3. 정점 yy에서 가장 먼 정점 zz를 찾는다.

 

하나의 함수로 입력값의 개수에 따라 가장 먼 정점과 정점 사이의 거리를 반환하게 하였다.

• 입력값이 node 하나 -> 가장 먼 거리의 node 반환
• 입력값이 node 두개 -> 두 node 사이의 거리 반환

 

import sys
from collections import deque
input = sys.stdin.readline


def BFS(start, finish=0):
    global N

    dq = deque()
    dq.append((start, 0))

    res = [0, 0]
    visited = [0] * (N+1)

    while dq:
        f, add = dq.popleft()
        visited[f] = 1

        for info in graph[f]:
            t = info[0]
            l = info[1]

            if t == finish:
                return add+l

            if visited[t]:
                continue

            if res[1] < add + l:
                res = [t, add+l]

            dq.append((t, add+l))

    return res[0]


N = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(N):
    ins = list(map(int, input().split()))

    cnt = 1
    while True:
        if ins[cnt] == -1:
            break

        if not cnt % 2:
            graph[ins[0]].append((ins[cnt-1], ins[cnt]))
        cnt += 1

u = BFS(1)
v = BFS(u)

print(BFS(u, v))

 

 

---

참고블로그

 

https://blog.myungwoo.kr/112

트리의 지름 구하기

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 파이썬)