백준 1167 파이썬 가장 긴 경로를 찾는 방법 관련 아이디어
2024. 5. 18. 06:54ㆍ코딩 도구/백준
반응형
백준 1167 - 트리의 지름
문제
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
답안 코드 :
from collections import deque
N = int(input())
A = [[] for _ in range(N + 1)]
for _ in range(N):
Data = list(map(int, input().split()))
index = 0
S = Data[index]
index += 1
while True:
E = Data[index]
if E == -1:
break
V = Data[index + 1]
A[S].append((E, V))
index += 2
distance = [0] * (N + 1)
visited = [False] * (N + 1)
def BFS(v):
queue = deque()
queue.append(v)
visited[v] = True
while queue:
now_Node = queue.popleft()
for i in A[now_Node]:
if not visited[i[0]]:
visited[i[0]] = True
queue.append(i[0])
distance[i[0]] = distance[now_Node] + i[1]
BFS(1)
Max = 1
for i in range(2, N + 1):
if distance[Max] < distance[i]:
Max = i
distance = [0] * (N + 1)
visited = [False] * (N + 1)
BFS(Max)
distance.sort()
print(distance[N])
생각 :
# 문제 분석
# 가장 긴 경로를 찾는 방법 관련 아이디어가 필요하다
# 아이디어
# 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나
# 문제 풀이
# 그래프를 인접 리스트로 저장
# (노드, 가중치)로 표현하고 싶어서 노드를 튜플로 선언
# 임의의 노드에서 BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장
# 그렇게 하나의 노드로 다 방문하여 거리 리스트를 업데이트
# 위 과정에서 얻은 리스트에서 임의의 노드와 가장 먼 노드 찾기
# 그 노드부터 다시 BFS 수행
# 이제 여기서 얻은 리스트에서 가장 큰 값이 트리의 지름이다.
탐색 알고리즘 정리 블로그
탐색 알고리즘 정리
탐색 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다. 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이
mkisos.tistory.com
반응형
'코딩 도구 > 백준' 카테고리의 다른 글
백준 2343 파이썬 블루레이 (1) | 2024.05.20 |
---|---|
백준 1920 파이썬 이진 탐색 O(nlogn) 시간 복잡도 (14) | 2024.05.19 |
백준 1260 파이썬 DFS와 BFS를 구현할 수 있는가 (25) | 2024.05.16 |
백준 13023 파이썬 DFS의 시간 복잡도 O(V+E) (1) | 2024.05.15 |
백준 2023 파이썬 DFS 재귀함수 (2) | 2024.05.14 |