[백준 1967번] 파이썬 - 트리의 지름

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

1967번: 트리의 지름

 

 

# 조건

• 트리는 사이클이 없는 무방향 그래프
• 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재
• 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있다.
• 이 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

 

• 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다.
  • 정확히 정의하면 트리에 존재하는 모든 경로들 중 가장 긴 것의 길이
• 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해 출력하라

 

입력

• 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다.
• 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다.
  • 간선에 대한 정보는 세 개의 정수로 이루어져 있다.
  • 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고,
  • 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다.
  • 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고,
  • 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다.
• 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

 

접근 방법

• DFS를 이용하여 한 정점에서 모든 정점에 가는 길을 탐색해준다.
  • 경로를 추가해줄 때, 자식 노드에서 부모노드로 가는 경로도 추가해주어야 모든 경로를 탐색 가능하다.
  • result 변수를 통해 최댓값을 기록해주면 된다.
  • 노드의 개수가 10,000개 이므로 시간초과가 발생
  • 시간 초과 1

 

• 따라서, leaf_node에 대해서만 가는 길을 탐색해준다.
  • leaf_node를 찾는 방법은
  • 자식 노드가 없기 때문에, 부모 노드로 가는 경로 1개밖에 없다.
  • pypy로 통과하지만 python은 시간 초과
  • 시간 초과 2

 

• 탐색 시간을 줄인다 = 탐색 노드의 수가 적다
  • 루트 노드가 1번으로 고정되어있으므로
  • 루트 노드에서 가장 경로 가중치가 높은 리프 노드 탐색 후 return
  • 그 노드에서 dfs를 진행해주면 될 것 같다.
  • pass code

 

시간초과 1 -> 모든 경로

import sys
input = sys.stdin.readline


def dfs(start):
    global result
    visited = [0] * (N+1)
    visited[start] = 1
    stack = [(start, 0)]
    while stack:
        cur_node, cur_dist = stack.pop()
        if cur_dist > result:
            result = cur_dist
        visited[cur_node] = 1
        for node, dist in tree[cur_node]:
            if visited[node] == 0:
                stack.append((node, dist+cur_dist))

    return result

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

result = 0
for i in range(1, N+1):
    dfs(i)

print(result)

 

시간초과 2 - pypy통과, python 시간 초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
def dfs(start):  
    global result  
    visited = [0] * (N+1)  
    visited[start] = 1  
    stack = [(start, 0)]  
    while stack:  
        cur_node, cur_dist = stack.pop()  
        if cur_dist > result:  
            result = cur_dist  
        visited[cur_node] = 1  
        for node, dist in tree[cur_node]:  
            if visited[node] == 0:  
                stack.append((node, dist+cur_dist))  
  
    return result  
  
N = int(input())  
tree=[[] for _ in range(N+1)]  
for i in range(N-1):  
    a, b, c = map(int, input().split())  
    # 부모 -> 자식 뿐만 아닌  
    # 자식 -> 부모 경로도 기록    tree[a].append((b,c))  
    tree[b].append((a,c))  
  
result = 0  
leaf_node = []  
# 모든 경로의 경우 시간초과가 발생  
# 따라서 리프 노드만 담아준다.  
for i in range(N+1):  
    if len(tree[i]) == 1:  
        leaf_node.append(i)  
  
for j in leaf_node:  
    dfs(j)  
  
print(result)

 

pass code

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
def dfs(start):  
    global idx, result  
    visited = [0] * (N+1)  
    visited[start] = 1  
    stack = [(start, 0)]  
    while stack:  
        cur_node, cur_dist = stack.pop()  
        if cur_dist > result:  
            result = cur_dist  
            idx = cur_node  
        visited[cur_node] = 1  
        for node, dist in tree[cur_node]:  
            if visited[node] == 0:  
                stack.append((node, dist+cur_dist))  
  
    return idx  
  
N = int(input())  
tree=[[] for _ in range(N+1)]  
for i in range(N-1):  
    a, b, c = map(int, input().split())  
    # 부모 -> 자식 뿐만 아닌  
    # 자식 -> 부모 경로도 기록 
    tree[a].append((b,c))  
    tree[b].append((a,c))  
  
result = 0  
idx = 0  
# 모든 경로의 경우 시간초과가 발생  
# 루트 노드에서 최대 거리 노드 반환  
dfs(1)  
  
dfs(idx)  
print(result)