티스토리 뷰

알고리즘/백준

1967번 트리의 지름 백준 파이썬

글을 쓰는 개발자 2020. 12. 15. 21:30
반응형

문제:www.acmicpc.net/problem/1967

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

import sys
from collections import deque
N=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,val=map(int,sys.stdin.readline().rstrip().split())
    graph[a-1].append([b-1,val])
    graph[b-1].append([a-1,val])

def bfs(start,mode):
    q=deque()
    val=[-1]*N
    val[start]=0
    q.append(start)
    while q:
        dot=q.popleft()
        for x in graph[dot]:
            if val[x[0]]==-1:
                val[x[0]]=x[1]+val[dot]
                q.append(x[0])
    
    if mode==1:
        return val.index(max(val))
    else:
        return max(val)

print(bfs(bfs(0,1),2))
 
 

참고:https://chldkato.tistory.com/29

 

백준 1967 트리의 지름 (파이썬)

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의..

chldkato.tistory.com

문제 접근은 최대길이가 되는 좌표를 찾아낸다. 그리고 그 좌표로부터 거리가 최대가 되는 것을 찾는다.

mode 1이 이제 루트로부터 거리가 최대인 좌표를 찾는 것이다.

mode 2는 최대인 좌표로부터 거리가 제일 큰 좌표를 찾는 것이다.

 

다른 풀이도 설명해보려 한다.

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def dimt(idx):
    global R
    if tree[idx]:
        large = 0
        small = 0
        for i, d in tree[idx]:
            now_distance = dimt(i)+d
            if now_distance > large:
                small = large
                large = now_distance
            elif now_distance > small:
                small = now_distance
        R = max(large + small, R)
        return large
    else:
        return 0


N = int(input())
tree = [[] for _ in range(N+1)]
N -= 1
R = 0
while N:
    parent, child, distance = map(int, input().split())
    tree[parent].append([child, distance])
    N -= 1
dimt(1)
print(R)
 
 

참고: 백준 파이썬 상위권 코드

반응형
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함