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

그래프, BFS/DFS 문제

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

 

트리의 지름

 

트리의 지름이란?

어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.

즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.

위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다.

 

트리의 지름을 구하는 순서

1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.
2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.
3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.

 

 

💡 풀이코드 (성공 - DFS)

# DFS
# visited 초기화 주의 

import sys 
sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())

graph = [[] * (n + 1) for _ in range(n + 1)] 
visited = [-1] * (n + 1)
for _ in range(n - 1):
    p, c, w = map(int, sys.stdin.readline().split())
    graph[p].append((c, w))
    graph[c].append((p, w))


def dfs(x, valSum):
    for i, w in graph[x]:
        if visited[i] == -1: 
            visited[i] = valSum + w # 방문 처리 
            dfs(i, valSum + w)

visited[1] = 0 # 1) 시작점인 루트 노드 방문처리
dfs(1, 0)
maxVal = max(visited)
maxIdx = visited.index(maxVal)

visited = [-1] * (n + 1)
visited[maxIdx] = 0 # 2) 시작점 노드 방문처리
dfs(maxIdx, 0)
print(max(visited))

 

접근 방식

• DFS
  • visited 배열을 만들고 -1로 초기화 -> 방문하지 않았다면 방문 후 해당 노드까지의 최댓값 기록 
  • return값 설정 X

 

주요 로직

1. DFS를 통해 루트 노드(1)로부터 가장 먼 정점(maxIdx)를 구한다.
2. DFS를 통해 구해진 (maxIdx) 정점으로부터 가장 먼 정점(z)를 구한다.
3. (maxIdx) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.
4. 트리의 지름의 값을 출력한다.

 

 

💡 풀이코드 (성공 - BFS)

# BFS
import sys 
from collections import deque 

sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())

graph = [[] * (n + 1) for _ in range(n + 1)] 
visited = [False] * (n + 1)
for _ in range(n - 1):
    p, c, w = map(int, sys.stdin.readline().split())
    graph[p].append((c, w))
    graph[c].append((p, w))

def bfs(start, val):
    global graph, visited

    queue = deque()
    queue.append((start, val))
    visited[start] = True # 1) 시작점 방문 처리
    
    result = (0, 0)
    while queue:
        idx, valSum = queue.popleft()
        for i, w in graph[idx]:
            if visited[i] == False:
                visited[i] = True # 2) 방문 처리
                queue.append((i, valSum + w))
                result = max(result, (valSum + w, i))

    return result
    
result = bfs(1, 0)
visited = [False] * (n + 1)
result = bfs(result[1], 0)
print(result[0])

 

접근 방식

• BFS
  • visited 배열을 만들고 False로 초기화 -> 방문하지 않았다면 방문 후 queue에 해당 노드까지의 최댓값 삽입
  • result에 기록된 노드-노드 사이의 최댓값과 비교하여 값이 더 크다면 업데이트

 

주요 로직

1. BFS를 통해 루트 노드(1)로부터 가장 먼 정점(y)를 구한다.
2. BFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.
3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.
4. 트리의 지름의 값을 출력한다.

 

 

참고문헌

https://kyun2da.github.io/2021/05/04/tree's_diameter/

[백준 / Python] 1967 트리의 지름 - Kyun2da Blog

https://edder773.tistory.com/271

[백준 1967] 트리의 지름(python)

https://dduniverse.tistory.com/entry/%EB%B0%B1%EC%A4%80-1967-1167-DFSBFS-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-%ED%8C%8C%EC%9D%B4%EC%8D%AC-python

백준 1967, 1167 | DFS/BFS | 트리의 지름 [파이썬 python]

https://jja2han.tistory.com/328

[백준 1967] - 트리의 지름(C++)[골드4]

https://johoonday.tistory.com/217

백준 No.1167 [트리의 지름]