백준 1167 트리의 지름

작성일 | In |

Problem : 트리의 지름

유형 : 그래프, BFS

문제 해석

  • 트리에서 임의의 두 점 사이 중 가장 긴 것을 구한다.

문제 재해석

  • 임의의 정점에서 가장 멀리 떨어진 정점을 구한다.
  • 위에서 구한 정점에서 가장 멀리 떨어진 정점과의 거리를 구한다.

해결 전략

  • 정점은 1부터 주어진다.
    • 1번 정점은 항상 존재한다.
  • 1번 정점로부터 가장 먼 정점을 찾는다.
    • 여기서 찾은 정점에서, 가장 먼 정점을 찾는다.
  • BFS를 이용해 트리를 순회한다.

설계, 구현

  • pair 를 이용해, 연결된 노드와 가중치를 저장한다.
  • 연결된, 방문하지 않은 노드를 방문한다.
    • 가중치를 더해가며 처음 시작한 노드로부터의 거리를 구한다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define pp pair<int, int>

using namespace std;

vector<pp> node[100002];
int dist[100002];
bool visit[100002];
int n;

queue<int> q;

int bfs(int i){

    int ret_dist = 0;
    int ret_node = 0;

    while(!q.empty()){
        auto cur_node = q.front(); q.pop();

        for(auto nxt : node[cur_node]){
            int nxt_node = nxt.first;
            int nxt_dist = nxt.second;

            if(visit[nxt_node]) continue;
            visit[nxt_node] = true;
            dist[nxt_node] = dist[cur_node] + nxt_dist;

            if(ret_dist < dist[nxt_node]){
                ret_dist = dist[nxt_node];
                ret_node = nxt_node;
            }

            q.push(nxt_node);
        }
    }

    if(i) return ret_node;
    else return ret_dist;
}

void solve() {
    visit[1] = true;
    q.push(1);
    int start = bfs(1);

    memset(dist, 0, sizeof(dist));
    memset(visit, false, sizeof(visit));

    visit[start] = true;
    q.push(start);

    cout << bfs(0);
}

void input() {
    cin >> n;

    int node_num;
    for (int i = 0; i < n; ++i){
        cin >> node_num;
        int a, b;
        while(1){
            cin >> a;
            if(a == -1) break;
            cin >> b;
            node[node_num].push_back({a,b});
        }
    }
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);  cout.tie(NULL);
   freopen("input.txt", "r", stdin);

   input();
   solve();

   return 0;
}

피드백

없음