알고리즘 스터디
[백준] 1967번 : 트리의 지름 - Python(파이썬)
히치키치
2021. 7. 13. 14:26
문제
https://www.acmicpc.net/problem/1967
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
정리
- 어떤 정점에서 제일 멀리 떨어진 정점 -> 원의 지름
- BFS
- root에서 각 노드까지 경로 값 구하기 -> 경로 값의 최대값의 노드 구하기 -> 해당 노드에서 가장 멀리 떨어진 노드의 경로 값 = 원의 지름
예제 이해
DFS / BFS
from collections import deque
def bfs(graph, start, visited):
# 시작 값으로 큐 초기화
queue=deque([start])
# 시작 노드 방문 처리
visited[start]=True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v=queue.popleft()
print(v, end=' ')
# 방문하지 않은 인접 노드들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
def dfs(graph, v, visited):
# 현재 노드를 방문처리
visited[v]=True
print(v,end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)[이론]파이썬 알고리즘 - DFS / BFS
많은 양의 데이터 중에서 원하는 데이터를 찾는 방법DFS / BFS는 그래프 탐색 알고리즘자기 자신을 다시 호출하는 함수스택 대신 재귀함수를 사용해서 구현하는 경우도 많음파이썬에서는 재귀함
velog.io
코드
#문제 : https://www.acmicpc.net/problem/1967
from collections import deque
import sys
input = sys.stdin.readline
def bfs(x, mode):
q = deque()
q.append(x) #시작점 enque
visit = [-1 for _ in range(n)] #방문 여부 배열
visit[x] = 0
while q:
x = q.popleft()
for w, nx in tree[x]:#경로가 연결 되어 있고
if visit[nx] == -1: #아직 방문 전
visit[nx] = visit[x] + w #가중치 더해서 갱신
q.append(nx)
if mode == 1:
return visit.index(max(visit)) #최대 경로 값 가진 노드 인덱스 반환
else:
return max(visit) #최대 경로 값
n = int(input()) #노드 갯수
tree = [[] for _ in range(n)]
for i in range(n-1):
x, y, w = map(int, input().split()) #간선에 대한 정보 입력
tree[x-1].append([w, y-1]) #양방향 연결 (index 0부터 시작해서 노드 번호-1)
tree[y-1].append([w, x-1])
print(bfs(bfs(0, 1), 2))