[백준/dfs] 1967번: 트리의 지름

-문제:https://www.acmicpc.net/problem/1967

노드말고 간선 가중치까지 주어져서 어떻게 그래프를 구현해야할지 고민이 많았던 문제다 

 트리의 지름은 결국 잎노드에서 잎노드로 이루어진다고 생각했어서 잎노드를 구하고 잎노드-잎노드 사이의 가중치를 모두 구한 후 거기서 최댓값을 구하는 거라고 생각했는데, 메모리 초과가 발생했다.

(경험상 모든 것을 다 탐색하는 거는 시간초과, 메모리초과가 발생한다. 효율적으로 코드 작성하는 거 연습하기. 7/30)

 

그 외에는 모르겠어서 구글링을 해보았더니 

그래프 구현은 노드에 연결된 노드와 간선 가중치를 모두 삽입하는 것으로 진행하는 것 같다 

 

1. 루트노드에서 가장 먼 노드를 dfs로 구한다음(1노드에서 가장 먼거)

2. 1번에서 구한 가장 먼 노드에서 한번 더 가장 먼 노드를 dfs로 구현한다 

3. 2번에서 구한 길이 중 가장 먼 길이가 정답이 된다 

-정답풀이: 

import sys
sys.setrecursionlimit(10**5)

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

def dfs(x,weight):
    for i in graph[x]:
        a,b=i
        if distance[a]==-1:
            distance[a]=weight+b
            dfs(a,weight+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))

-풀이 이해: 

x와 이어진 i번째 노드에 대하여 

i번째 노드와 연결된 노드와 가중치를  a,b에 입력한 후 

연결된 노드를 방문하지 않았다면 distance[a]에 주어진 무게와 가중치를 넣고 이동시킨다 

dfs 다시 실행

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

 

각 노드에 연결된 노드와 가중치를 넣어서 그래프를 구현한다 

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

 

1의 weight는 0 이므로 방문하지 않은 노드의 값을 0으로 하면 안되기에 -1로 distance를 초기화 해준다 

dfs(1,0)을 통해 1에서 가장 먼 노드를 구한다 

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

루트 노드로부터 가장 멀리에 있는 노드를 구한다(distance가 최대인 인덱스의 값을 구하는 것)

distance 다시 한번 더 초기화 하고, 

가장 먼 노드를 루트노드로 두고 dfs를 진행한다 

start=distance.index(max(distance))
distance=[-1]*(n+1)
distance[start]=0
dfs(start,0)

print(max(distance))