[백준/Baekjoon] 1167 트리의 지름 C++ :: Graph & DFS

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

1167번: 트리의 지름

---

1. Logic

- 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.라고 문제에서 그러는데 이게 무슨말이지 싶을것이다.

아래 그림을 보자

아무 점 하나를 나는 1로 잡을 것이다. 1에서 경로가 가장 먼 노드를 찾으면 2 + 4 + 5 =11로 4번 노드이다. 이제 여기서 DFS를 다시 돌아서 나오는 정점까지의 거리가 트리의 지름인데 계산해보면 4번노드 -> 3번노드까지의 거리가 5+4+5=14로 가장 길다. 그러므로 트리의 지름은 14가 되는 것이다.

 

즉 말 그대로 임의정 정점에서 DFS를 돌며 가장 먼 노드를 찾고 그 정점에서 다시 DFS를 돌아서 찾은 가장 먼 노드까지의 거리가 트리의 지름이 되는 것이다. DFS로 됐으니 당연히 BFS도 구현 가능하다.

밑에 DFS와 BFS 둘다 구현해놨으므로 코드를 참고하자

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int dist[100001];
int vis[100001];
int maxCost = 0;
int deepestNode = 0;
vector<pair<int, int>> graph[100001];

void DFS(int cur, int cost) {
    if(cost > maxCost) {
        maxCost = cost;
        deepestNode = cur;
    }

    vis[cur] = true;

    for(int i = 0; i < graph[cur].size(); i++) {
        int next = graph[cur][i].first;
        int ncost = graph[cur][i].second;

        if(vis[next]) continue;

        DFS(next, cost + ncost);
    }
}

void BFS(int firstNode, int firstCost) {
    queue<pair<int, int>> q;
    q.push({firstNode, firstCost});
    vis[firstNode] = true;

    while(!q.empty()) {
        int cur = q.front().first;
        int cost = q.front().second;
        vis[cur] = true;
        q.pop();
        
        for(int i = 0; i < graph[cur].size(); i++) {
            int next = graph[cur][i].first;
            int ncost = graph[cur][i].second;

            if(vis[next]) continue;
            q.push({next, cost + ncost});
            if(cost + ncost > maxCost) {
                maxCost = cost + ncost;
                deepestNode = next;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;

    for(int i = 0; i < n; i++) {
        int nodeNum;
        cin >> nodeNum;
        int input, value;
        while(true) {
            cin >> input;
            if(input == -1) break;
            cin >> value;
            
            graph[nodeNum].push_back({input, value});
        }
    }

    //DFS(1, 0);
    BFS(1, 0);
    maxCost = 0;
    memset(vis, false, sizeof(vis));

    //DFS(deepestNode, 0);
    BFS(deepestNode, 0);
    cout << maxCost;
}

---

3. Feedback

이 문제도 처음에 이해를 하지 못해서 섣불리 구현을 하지 못했다. 문제 이해력이 부족한 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90