[백준 1167번] 트리의 지름 (C++ / Python)

아.. 결국 혼자서 못풀고, 다른사람들의 풀이법을 보고 풀었다.

아이디어 얻고나서 무릎을 탁! 쳐버렸ㄷ.

아이디어

대충 아래와같은 트리가 있고, 

임의의 노드(여기서 1번 노드)에서 출발해서 가장 길이가 긴 노드를 찾는다. (5번 노드)

그럼 5번 노드부터 가장 길이가 긴 트리길이를 찾으면 

그것이 트리의 지름이 된다.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>> v[100001];
bool visited[100001];
int maxidx = 0;
int maxvalue = 0;

void dfs(int node, int sum)
{
    if( maxvalue < sum) // 가장 먼 node찾기.
    {
        maxvalue = sum;
        maxidx = node;
    }
    
    for(int i = 0 ; i< v[node].size(); i++)
    {
        if( visited[v[node][i].first] == false)
        {
            visited[v[node][i].first] = true;
            dfs(v[node][i].first, sum+ v[node][i].second);
            visited[v[node][i].first] = false;
        }
    }
    return; // 더이상 dfs 재귀 들어가지 않으면 return.
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    for(int i = 0 ; i< N; i++)
    {
        int s;
        cin >> s;
        while(1)
        {
            int e, d;
            cin >> e;
            if(e == -1) break;
            else {
                cin >> d;
                v[s].push_back({e,d});
            }
        }
    }
    visited[1] = true;
    dfs(1,0);
    
    memset(visited, false, sizeof(visited));
    visited[maxidx] = true;
    dfs(maxidx,0);
    cout << maxvalue ;
}

 

Python  풀이

import sys
input = sys.stdin.readline

V = int(input().rstrip())
li = [[] for _ in range(V+1)]
visited = [False] *(V+1)
maxidx = 0
maxvalue = 0
for i in range(1,V+1):
    l = list(map(int,input().rstrip().split()[:-1]))
    s = l[0]
    e = 1
    while True:
        if e+2 > len(l):
            break;
        li[s].append(l[e:e+2])
        e +=2
    
def dfs(node,sum):
    global li, visited, maxidx, maxvalue
    if maxvalue < sum:
        maxvalue = sum
        maxidx = node
    
    for info in li[node]:
        n = info[0]
        w = info[1]
        if visited[n] == False:
            visited[n] = True
            dfs(n, sum+w)
            visited[n] = False
    return

visited[1] = True
dfs(1,0)

visited = [False] * (V+1)
visited[maxidx] = True
dfs(maxidx,0)

print(maxvalue)

아니 인풋 어떻게 받아야되나 했더니 

for i in range(1,V+1):
    l = list(map(int,input().rstrip().split()))
    l.pop()
    s = l[0]
    for i in range(1,len(l),2):
        li[s].append([l[i], l[i+1]])

이렇게 받으면 편하다...