알고리즘/백준[baekjoon]
[baekjoon] 백준 1167번 : 트리의 지름 (by python 파이썬) bfs, tree
코딩하는이씨
2022. 8. 16. 13:00
728x90
반응형
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
정답 code
#트리의 지름
from collections import deque
import sys
input = sys.stdin.readline
def bfs(s):
queue = deque()
visit = [-1] * (v+1)
queue.append(s)
visit[s] = 0
node_distance = [0,0]
while queue:
q = queue.popleft()
for x, y in tree[q]:
if visit[x] == -1:
visit[x] = visit[q]+ y
queue.append(x)
if node_distance[1] < visit[x] :
node_distance = x, visit[x]
return node_distance
v = int(input())
tree = [[] for _ in range(v+1)]
for _ in range(v):
c = list(map(int,input().split()))
#입력값이 노드번호, 거리 임으로 두칸씩 건너뜀
for i in range(1, len(c) - 2, 2):
#트리에 이어진 노드번호, 거리 저장
tree[c[0]].append((c[i], c[i + 1]))
#출발노드상관 x부터 가장 멀리있는 노드와 거리 구함
node, distance = bfs(1)
#출발노드에서 가장멀리 있는 노드에서 가장 멀리있는 노드를 구하면 트리의 지름
node, distance = bfs(node)
print(distance)
solution
트리의 지름을 구하는 방법은 아무노드에서 부터 시작하여 제일 멀리 있는 노드를 찾은다음,
그 노드로 부터 가장 멀리있는 노드까지의 거리를 찾으면 된다.
트리의 지름 구하기
트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를
blog.myungwoo.kr
위 블로그에 자세한 설명이 나와있다.
해당 코드를 짜면서 문제가 됬던 부분은 visit리스트를 처음에 만들때 False로 만들고 시작했는데 False가 0이고 True가 1의 값을 가져오류가 발생했다. 결국 처음에 -1로 초기화 하여 시작하였다.
728x90
반응형