티스토리 뷰
728x90
https://www.acmicpc.net/problem/1967
- 문제 :
트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.
이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.
입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.
트리의 노드는 1부터 n까지 번호가 매겨져 있다.
- 풀이 :
트리에서 가중치를 통해 가장 먼 노드 2개를 찾는 문제이다.
시작점에서 가장 먼 노드를 찾고, 이 노드로부터 가장 먼 노드를 찾으면 그 결괏값이 가장 먼 노드이다.
따라서 bfs 두 번으로 해결할 수 있다.
V와 E의 맥스값이 10000이므로 bfs의 시간복잡도인 O(V+E)내에 해결할 수 있다.
- 소스코드 :
from collections import deque
def bfs(start):
visited = [-1] * (N + 1)
visited[start] = 0
queue = deque()
queue.append(start)
while queue:
curr = queue.popleft()
for i,cost in tree[curr]:
if visited[i] == -1:
queue.append(i)
visited[i] = visited[curr] + cost
m = max(visited)
return [visited.index(m),m]
N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
start,end,weight = map(int,input().split())
tree[start].append([end,weight])
tree[end].append([start,weight])
print(bfs(bfs(1)[0])[1])
320x100
'Algorithm > DFS & BFS' 카테고리의 다른 글
(Python) - BOJ(13549번) : 숨바꼭질 3 (0) | 2022.03.04 |
---|---|
(Python) - BOJ(1520번) : 내리막 길 (0) | 2022.03.03 |
(Python) - BOJ(11725번) : 트리의 부모 찾기 (0) | 2022.03.03 |
(Python) - BOJ(2206번) : 벽 부수고 이동하기 (0) | 2022.03.02 |
(Python) - BOJ(12851번) : 숨바꼭질 2 (0) | 2022.03.02 |
댓글
© 2022 WonSeok, All rights reserved