백준 1167(트리의 지름) - Python

접근

1.트리를 어떻게 표현해야할까. 배열 ? 그래프?

예제 입력 케이스를 보니 그래프가 편할거 같아서 선택

2.어떤 정점부터 그래프 탐색을 진행해야 지름을 구할 수 있을까.

리프 노드에서 리프 노드까지일텐데 그래프의 length가 1인 경우를 구하면 되려나?

1번 노드에 2, 3, 4, 5 , 6, 7 번 노드가 연결된 경우를 생각해보자

                    (1)

       1    2    3   4   5   6

(2)  (3)  (4)      (5)  (6)  (7) 

이런 그래프가 있다면 (7) -> (1) -> (6) 을 방문하는 경우가 최대인데 안되겠다.

근데 어떤곳에서 그래프 탐색을 탐색을 하면 가장 먼 노드가 구해지고 그 노드부터 가면 최대값이 구해지겠다.

 

bfs와 dfs로 둘다 풀어보자!

 

나의 코드1 (dfs)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
maxv = 0
maxn = 0
G = [[] for _ in range(n+1)]
for i in range(n):
    t = list(map(int,input().split()))[:-1]
    for j in range(1,len(t)-1,2):
        G[t[0]].append((t[j],t[j+1]))


def dfs(i,value):
    global maxv
    global maxn
    for nextnode, nvalue in G[i]:
        if not visit[nextnode]:
            visit[nextnode] = True
            dfs(nextnode, value+nvalue)
            if maxv < value+nvalue:
                maxv = value+nvalue
                maxn = nextnode


visit = [False for _ in range(n+1)]
visit[1] = True
dfs(1,0)
visit = [False for _ in range(n+1)]
visit[maxn] = True
dfs(maxn,0)
print(maxv)

 

나의 코드2 (bfs)

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

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

def bfs(i):
    visit = [-1 for _ in range(n+1)]
    M = deque()
    M.append(i)
    visit[i] = 0
    maxv = [0,0]
    while M:
        index = M.popleft()
        for j, value in G[index]:
            if visit[j] == -1:
                visit[j] = visit[index]+value
                M.append(j)
                if visit[j] > maxv[0]:
                    maxv[0] = visit[j]
                    maxv[1] = j
    return maxv

m1, i1 = bfs(1)
m2, i2 = bfs(i1)
print(m2)