BOJ/백준 1967 트리의 지름

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

 

해결 아이디어

먼저 정점 노드에서 dfs를 진행해서 가장 먼 노드를 찾은 후 가장 먼 노드에서 dfs 를 진행

 

 

#include<iostream>
#include<vector>
using namespace std;

// 트리를 인접 리스트 형태로 표현하기 위한 자료구조
vector<vector<pair<int, int>>> tree;
// 방문 여부를 체크하는 배열
vector<bool> visited;  

// DFS 함수: 현재 노드에서 다른 노드들까지의 거리를 계산
void dfs(int cur, vector<int>& dist) {
    int len = tree[cur].size();  // 현재 노드의 자식 노드 개수
    for (int i = 0; i < len; i++) {
        int next_node = tree[cur][i].first;  // 자식 노드
        int weight = tree[cur][i].second;  // 현재 노드와 자식 노드 간의 거리 (가중치)
        if (visited[next_node]) continue;  // 이미 방문한 노드는 건너뜀
        visited[next_node] = true;  // 다음 노드를 방문했음을 표시
        dist[next_node] = dist[cur] + weight;  // 현재 노드까지의 거리 + 가중치 = 다음 노드까지의 거리
        dfs(next_node, dist);  // 재귀적으로 DFS 호출
    }
}

int solve() {
    int max_node = 1;  // 가장 먼 노드를 저장할 변수
    vector<int> dist(tree.size(), 0);  // 노드 간의 거리를 저장하는 배열
    visited.assign(tree.size(), false);  // 방문 배열 초기화
    visited[1] = true;  // 루트 노드(1번 노드) 방문 표시

    // 첫 번째 DFS: 루트(1번 노드)에서 가장 먼 노드를 찾음
    dfs(1, dist);

    // dist에서 가장 먼 노드를 찾음
    int max_dist = 0;  // 최대 거리 초기화
    for (int i = 1; i < dist.size(); i++) {
        if (dist[i] > max_dist) {  // 현재 거리 값이 최대 거리보다 크면
            max_dist = dist[i];  // 최대 거리 업데이트
            max_node = i;  // 가장 먼 노드 저장
        }
    }

    // 두 번째 DFS를 위한 준비
    dist.assign(tree.size(), 0);  // 거리 배열 초기화
    visited.assign(tree.size(), false);  // 방문 배열 초기화
    visited[max_node] = true;  // max_node에서 시작

    // 두 번째 DFS: max_node에서 다시 가장 먼 노드를 찾음
    dfs(max_node, dist);

    // 두 번째 DFS에서의 최장 거리를 찾음
    max_dist = 0;  // 최대 거리 초기화
    for (int i = 1; i < dist.size(); i++) {
        if (dist[i] > max_dist) {
            max_dist = dist[i];  // 최장 거리 값 업데이트
        }
    }

    return max_dist;  // 트리의 지름 반환
}

int main(){
    ios::sync_with_stdio(0);  // 입출력 성능 향상
    cin.tie(0);  // cin과 cout의 동기화 끄기
    
    int n;  // 노드 개수
    cin >> n;  // 노드 개수 입력
    tree.resize(n + 1);  // 노드 개수에 맞게 트리 사이즈 조정

    // 트리의 간선 입력 받기
    for (int i = 0; i < n - 1; i++) {
        int x, y, z;  // 노드 x, y와 간선의 가중치 z
        cin >> x >> y >> z;  // 간선 정보 입력
        tree[x].push_back({y, z});  // x에서 y로 가는 간선 추가
        tree[y].push_back({x, z});  // y에서 x로 가는 간선 추가 (무향 그래프)
    }

    // 트리의 지름 출력
    cout << solve() << '\n';  // solve() 함수 호출 및 결과 출력
    return 0;  // 프로그램 종료
}