[백준] 1967번 : 트리의 지름 - Python(파이썬)

문제

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

정리

• 어떤 정점에서 제일 멀리 떨어진 정점 -> 원의 지름
• 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)

https://velog.io/@jiffydev/%EC%9D%B4%EB%A1%A0%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS

[이론]파이썬 알고리즘 - DFS / BFS

 

 

코드

#문제 : 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))