DFS 2번으로 트리의 지름을 구하는 방법

1. 문제

 

1967번: 트리의 지름 (acmicpc.net)

1967번: 트리의 지름

 

2. 풀이1

 

트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이 모든 경로가 유일하다.

 

가장 길이가 긴 경로를 트리의 지름이라고 정의했는데..

 

어쨌든 가장 길이가 긴 경로라면 결국 리프 노드와 리프 노드 사이 거리가 가장 길이가 긴 경로이다.

 

루트 노드가 1번 노드이고 (부모, 자식)으로 입력이 주어지니까 부모 노드 모두 표시해두면

 

표시가 안된 노드는 어떤 노드의 부모가 아니니까 리프 노드가 된다

 

이 리프 노드를 모두 찾고 해당 리프 노드에서 시작해서 DFS 탐색해가지고 가중치를 더해가면서 경로의 최대 길이를 갱신해나간다

 

 

 

근데 모든 리프 노드에서 탐색하면 시간 초과 가능성이 높다

 

8번부터 시작해서 9번, 7번, 4번, 5번 노드로 각각 탐색하면서 길이를 구할텐데,

 

8번에서 7번으로 가는 경로랑

 

7번부터 시작해서 8번, 9번, 4번, 5번 노드로 탐색하면서 길이를 구하다가..

 

7번에서 8번으로 가는 경로는 중복된 경로이다.

 

이런 경우를 줄여주고자 리프 노드를 모두 구하고, 처음부터 탐색하면서 이전 리프 노드는 방문처리해주고 DFS하면..

 

통과하긴함

 

from sys import stdin,setrecursionlimit
setrecursionlimit(10000)

def dfs(u,path):
    
    global diameter

    if diameter < path:
        
        diameter = path

    visited[u] = 1

    for v,w in tree[u]:
        
        if visited[v] == 0:
            
            dfs(v,path+w)

n = int(stdin.readline())

tree = [[] for _ in range(n+1)]
parent = [0]*(n+1)

for _ in range(n-1):
    
    a,b,w = map(int,stdin.readline().split())

    tree[a].append((b,w))
    tree[b].append((a,w))

    parent[a] = 1

diameter = 0

leaf = []

for i in range(1,n+1):
    
    if parent[i] == 0:
        
        leaf.append(i)

visited = [0]*(n+1)
dfs(leaf[0],0)

for i in range(1,len(leaf)):
    
    visited = [0]*(n+1)

    for j in range(i):
        
        visited[leaf[j]] = 1
    
    dfs(leaf[i],0)
    
print(diameter)

 

 

3. 풀이2

 

근데 조금 더 생각해보면...

 

트리의 지름은 결국 가장 멀리있는 노드와 가장 멀리 있는 노드 사이 거리가 될 것이다.

 

먼저 처음에 아무 노드에서 DFS를 수행해서 가장 멀리 있는 노드를 찾는다

 

1번에서 시작한다면 8번이 된다거나..

 

3번에서 시작한다면 8번이 된다거나..

 

9번에서 시작한다면 5번이 된다거나..

 

 

 

 

진짜 아무 노드에서 시작해서 가장 먼 노드를 찾는다면...

 

그 가장 먼 노드에서 DFS를 시작해서 가장 길이가 긴 경로를 찾는다면... 그것이 트리의 지름이 될 것이다.

 

이러면 2번의 DFS만으로 지름을 찾아낼 수 있다.

 

 

 

 

루트가 1번이라고 고정되어있으니 루트에서 시작해서 가장 먼 노드를 찾고 그 노드에서 가장 길이가 긴 경로를 찾는다

 

#트리의 지름을 찾는 방법
from sys import stdin,setrecursionlimit
setrecursionlimit(100000)

def dfs(u,path):
    
    global diameter,leaf

    if diameter < path:
        
        diameter = path
        leaf = u
        
    visited[u] = 1

    for v,w in tree[u]:
        
        if visited[v] == 0:
            
            dfs(v,path+w)

n = int(stdin.readline())

tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    
    a,b,w = map(int,stdin.readline().split())

    tree[a].append((b,w))
    tree[b].append((a,w)) #리프에서 리프로 가는 경로를 찾아야해서, 자식 - 부모도 넣어준다

#아무 노드에서나 시작해서, 가장 멀리있는 노드(leaf)를 찾는다
diameter = 0
leaf = -1
visited = [0]*(n+1)
dfs(1,0)

#가장 멀리 있는 노드(leaf)에서 시작해서 가장 길이가 긴 경로를 찾으면 그것이 트리의 지름
visited = [0]*(n+1)
dfs(leaf,0)

print(diameter)