[BOJ][1167] 트리의 지름

1. 문제 링크

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

2. 사용 알고리즘

트리, BFS

3. 풀이

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

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

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

4. 소스 코드

4-1. C++

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

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

using namespace std;

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

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; ++i) {
        int u; cin >> u;
        while(1) {
            int v; cin >> v;
            if(v == -1) break;
            int d; cin >> d;
            arr[u].push_back(make_pair(v, d));
        }
    }
    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/1167.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[100003];
    static int[] dist = new int[100003];
    static int[] check = new int[100003];

    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; ++i) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            while(true) {
                int v = Integer.parseInt(st.nextToken());
                if(v == -1) break;
                int d = Integer.parseInt(st.nextToken());
                arr[u].add(new Pair(v, d));
            }
        }
        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;
                }
            }
        }
    }
}