[BOJ][1967] 트리의 지름

1. 문제 링크

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

2. 사용 알고리즘

트리, BFS

3. 풀이

단계별로 진행한다는 BFS의 성질을 이용

1) 1번 노드부터 BFS 탐색을 하며 거리를 구하여, 거리가 가장 긴 노드 확인

2) 거리가 가장 긴 노드부터 다시 BFS 탐색을 하며 거리를 구하여, 가장 긴 거리가 트리의 지름

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1967.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int ,int>> arr[10003];
int dist[10003];
int check[10003];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    check[start] = 1;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        int len = arr[node].size();
        for(int i = 0; i < len; ++i) {
            if(check[arr[node][i].first] == 0) {
                check[arr[node][i].first] = 1;
                q.push(arr[node][i].first);
                dist[arr[node][i].first] = dist[node] + arr[node][i].second;
            }
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for(int i = 0; i < n - 1; ++i) {
        int u, v, w; cin >> u >> v >> w;
        arr[u].push_back(make_pair(v, w));
        arr[v].push_back(make_pair(u, w));
    }
    bfs(1);
    int maxNode = -1, maxDist = -1;
    for(int i = 1; i <=n; ++i) {
        if(dist[i] > maxDist) {
            maxDist = dist[i];
            maxNode = i;
        }
        dist[i] = 0;
        check[i] = 0;
    }
    bfs(maxNode);
    maxDist = -1;
    for(int i = 1; i <=n; ++i) {
        if(dist[i] > maxDist) {
            maxDist = dist[i];
        }
    }
    cout << maxDist << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1967.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair {
    int node, dist;
    Pair(int node, int dist) {
        this.node = node;
        this.dist = dist;
    }
}

public class Main {

    static List<Pair>[] arr = new List[10003];
    static int[] dist = new int[10003];
    static int[] check = new int[10003];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 1; i <= n; ++i) arr[i] = new ArrayList<>();
        StringTokenizer st;
        for(int i = 0; i < n - 1; ++i) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[u].add(new Pair(v, w));
            arr[v].add(new Pair(u, w));
        }
        bfs(1);
        int maxNode = -1, maxDist = -1;
        for(int i = 1; i <= n; ++i) {
            if(dist[i] > maxDist) {
                maxDist = dist[i];
                maxNode = i;
            }
            dist[i] = 0;
            check[i] = 0;
        }
        bfs(maxNode);
        maxDist = -1;
        for(int i = 1; i <=n; ++i) {
            if(dist[i] > maxDist) {
                maxDist = dist[i];
            }
        }
        System.out.println(maxDist);
    }

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        check[start] = 1;
        while(!q.isEmpty()) {
            int node = q.remove();
            int len = arr[node].size();
            for(int i = 0; i < len; ++i) {
                if(check[arr[node].get(i).node] == 0) {
                    check[arr[node].get(i).node] = 1;
                    q.add(arr[node].get(i).node);
                    dist[arr[node].get(i).node] = dist[node] + arr[node].get(i).dist;
                }
            }
        }
    }
}