[백준/Python] 1967번(DFS)_트리의 지름

📌문제 유형

그래프 이론, 그래프 탐색, 트리, DFS (골드 Lv.4)

 

📌문제

1967번: 트리의 지름

 

📌나의 문제풀이

- 모든 노드 다 방문해서 DFS하면 시간 초과 → leaf node만 DFS, 이것도 시간초과 

- 최종 방법 : 노드 1에서 가장 먼 노드 하나 선택 → 가장 먼 노드에서 시작하여 끝나는 지점이 가장 먼것이 최대 지름

• DFS 두 번 사용한 방법!

import sys
sys.setrecursionlimit(10**5)

n = int(input())
graphs = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, dist = map(int, sys.stdin.readline().split())
    graphs[a].append([b, dist])
    graphs[b].append([a, dist])


def dfs(i,total,visited):
    global max_,num

    if total > max_:
        max_ = total
        num = i
        
    for node, dis in graphs[i]:
        if visited[node] == 0:
            visited[node] = 1
            dfs(node, total + dis,visited)
            

# 1에서 가장 먼 노드 찾기
visited = [0 for _ in range(n+1)]
max_,num = 0,0
dfs(1,0,visited)

# 최대값 찾기
ans = 0
visited = [0 for _ in range(n+1)]
visited[num] = 1
max_ = 0
dfs(num,0,visited)

if max_ > ans:
    ans = max_
print(ans)

 

📌 다른사람의 문제풀이

- 동일한 방법, DFS 구성이 다름

• distance 자체를 배열로 만들어서 갱신하기
• global 보다 덜 복잡

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
graph = [[] for _ in range(n + 1)]


def dfs(x, wei):
    for i in graph[x]:
        a, b = i
        if distance[a] == -1:
            distance[a] = wei + b
            dfs(a, wei + b)


# 트리 구현
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

# 1번 노드에서 가장 먼 곳을 찾는다.
distance = [-1] * (n + 1)
distance[1] = 0
dfs(1, 0)

# 위에서 찾은 노드에 대한 가장 먼 노드를 찾는다.
start = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[start] = 0
dfs(start, 0)

print(max(distance))

 

📌 리뷰

• leaf node까지 생각한건 좋았는데, 조금 더 생각했으면 답지 안보고 풀 수 있었을 듯
• 하단의 블로그 풀이순서 참고하여 코드 짬

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