[BOJ/백준] 1167 트리의 지름

● [문제번호 1167] 트리의 지름

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

● 알아야 할 것

: vector 자료구조와 메소드

: pair 자료구조와 메소드

: BFS, DFS(재귀)

 

 

● 풀이 과정

: BFS, DFS(재귀)로 모두 구현해봐도 정답도 잘 나오는데

계속 3%, 4%에서 '틀렸습니다'를 받았다.

무엇이 문제일지 고민하고 구글링해보니 모든 정점을 출발점으로 놓고 실행하면 통과하기 어렵다고 한다.

 

: 구글링에 의한 풀이과정은

1. 임의의 정점에서 가장 멀리 있는 정점을 구한다.

2. 그 정점에서 가장 멀리 있는 정점과의 거리가 최대 지름이다.

라는 것이다.

 

결국 정점이 몇개든 2번의 함수 실행을 통해 구할 수 있다는 것인데,

이해하기 어려워서 해설이나 증명을 찾아보았으나 완벽하게 이해하기 어려웠다.

참고 링크

 

 

● 주의 할 것

: 다른 구글링 풀이에서는 visited(방문기록)을 사용하지 않은 풀이가 있지만,

내가 푼 풀이에서는 사용했기에

2번째 함수를 실행하기 전에 방문기록 초기화를 해야한다.

 

 

● 참고 할 것

: 최대 지름 구하는 방법 증명

https://blog.myungwoo.kr/112

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// node : 트리 입력 (각 정점에서 연결된 {정점번호, 정점거리} 저장)
// visited : 방문기록
// diameter : 가장 긴 지름 저장
// stopover : 임의의 정점에서 가장 먼 노드 번호 저장
vector<pair<int, int>> node[100001];
bool visited[100001];
int V, diameter, stopover;

// 너비 우선 탐색
void bfs(int start)
{
    // Queue의 원소 {노드번호, start에서 노드까지 거리}
    queue<pair<int, int>> q;
    
    visited[start] = true;
    
    q.push(pair<int, int>(start, 0));
    
    while(!q.empty())
    {
        int from = q.front().first;
        int from_dist = q.front().second;
        
        // 최대 지름이 길어질 때 마다 갱신
        if(diameter < from_dist)
        {
            diameter = from_dist;
            stopover = from;
        }
        
        visited[from] = true;
        
        q.pop();
        
        for(int i = 0; i < node[from].size(); i++)
        {
            int to = node[from][i].first;
            int to_dist = node[from][i].second;
            
            if(!visited[to])
                q.push(pair<int, int>(to, from_dist + to_dist));
        }
    }
}

// 깊이 우선 탐색
// (현재 노드, 현재 노드까지 거리)
void dfs(int from, int dist)
{
    // 최대 지름이 길어질 때마다 갱신
    if(diameter < dist)
    {
        diameter = dist;
        stopover = from;
    }
    
    visited[from] = true;
    
    for(int i = 0; i < node[from].size(); i++)
    {
        int to = node[from][i].first;
        int to_dist = node[from][i].second;
        
        if(!visited[to])
            dfs(to, dist + to_dist);
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> V;
    
    // 트리 입력
    for(int v = 0; v < V; v++)
    {
        int n, a, b;
        
        cin >> n;
        
        while(1)
        {
            cin >> a;
            
            if(a == -1)
                break;
            
            cin >> b;
            
            node[n].push_back(pair<int, int>(a, b));
        }
    }
    
    // BFS, DFS(재귀) 중 선택하여 실행
    dfs(1, 0);
    fill(visited, visited + 100001, false);
    dfs(stopover, 0);
    
    // bfs(1);
    // fill(visited, visited + 100001, false);
    // bfs(stopover);
    
    cout << diameter;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [620 - 트리 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1991	트리 순회	https://pirateturtle.tistory.com/288
2	2250	트리의 높이와 너비	https://pirateturtle.tistory.com/289
3	11725	트리의 부모 찾기	https://pirateturtle.tistory.com/290
4	1167	트리의 지름	https://pirateturtle.tistory.com/291
5	1967	트리의 지름	https://pirateturtle.tistory.com/292