[Python] 1967 - 트리의 지름

[Gold IV] 트리의 지름 - 1967 

[문제 링크](https://www.acmicpc.net/problem/1967)

🗝️알고리즘 분류

• 트리의 탐색
• 깊이 우선 탐색(DFS)

---

💻문제 정의

주어진 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 구하는 문제이다.

 

💡접근 및 설계

문제에서 트리의 루트 노드는 항상 1번 노드라고 명시되어 있다. 따라서 루트 노드로 부터 가장 멀리 떨어진 노드를 찾고, 해당 노드에서 부터 가장 멀리 떨어진 노드를 찾은 다음, 두 노드 사이의 거리를 구하는 방식으로 접근하였다.

 

✏️알고리즘 풀이

graph = [[] for _ in range(N+1)] # 트리 초기화

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

먼저 양방향 트리를 정의한다. a는 항상 b의 부모노드가 되고, c는 a와 b 사이의 길이를 나타낸다.

 

양방향 트리로 정의하는 이유는 DFS를 두 번 진행하기 때문이다. (루트 노드에서 한 번, 루트 노드와 가장 멀리 떨어진 노드에서 한 번)

 

# 방문(길이) 표시
visited = [-1 for _ in range(N+1)]
visited[1] = 0 # 루트 노드에선 길이 0

# DFS 탐색
def dfs(num, length):
    for a, b in graph[num]:
        if (visited[a] == -1):
            visited[a] = b + length # 현재의 길이와 하위 노드로 갈 때의 길이 합을 저장
            dfs(a, visited[a])

# 루트에서부터 모든 노드까지의 거리 탐색
dfs(1, 0)

start = visited.index(max(visited)) # 루트에서 부터 가장 멀리 떨어진 노드

visited = [-1 for _ in range(N+1)] # 방문 초기화
visited[start] = 0

dfs(start, 0) # start로부터 모든 노드까지의 거리 탐색

탐색을 시작할 노드와의 길이를 저장할 리스트를 정의한다. 첫 번째 탐색은 루트 노드 (1번 노드)에서 부터 시작할 것이니 visited[1]은 0으로 정의한다.

 

DFS 진행 과정에서, 자식 노드가 길이가 정의되지 않은(즉, 방문하지 않은) 노드일 경우 현재까지의 길이와 자식 노드까지의 길이를 더해준다.

 

이후 자식노드로 부터 DFS를 한다.

 

탐색이 종료되면 visited 리스트안에는 루트 노드로 부터 해당 노드까지의 길이가 각 인덱스 별로 저장되어 있다.

 

visited.index(max(visited))를 통해 길이가 가장 긴 값의 index를 가져온다. 해당 인덱스는 루트 노드와 가장 멀리 떨어진 노드의 번호가 된다.

 

해당 노드에서 부터 가장 멀리 떨어진 노드를 찾는 DFS를 진행한다.

 

🗒️전체 코드

# 1967 트리의 지름

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N = int(input())

graph = [[] for _ in range(N+1)] # 트리 초기화

for _ in range(N-1):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

# 방문(길이) 표시
visited = [-1 for _ in range(N+1)]
visited[1] = 0 # 루트 노드에선 길이 0

# DFS 탐색
def dfs(num, length):
    for a, b in graph[num]:
        if (visited[a] == -1):
            visited[a] = b + length # 현재의 길이와 하위 노드로 갈 때의 길이 합을 저장
            dfs(a, visited[a])

# 루트에서부터 모든 노드까지의 거리 탐색
dfs(1, 0)

start = visited.index(max(visited)) # 루트에서 부터 가장 멀리 떨어진 노드

visited = [-1 for _ in range(N+1)] # 방문 초기화
visited[start] = 0

dfs(start, 0) # start로부터 모든 노드까지의 거리 탐색

print(max(visited)) # 가장 긴 길이가 트리의 지름이 된다.

---

Do_ProgrammingTest/TIL/1967_트리의 지름.md at main · Do-heewan/Do_ProgrammingTest