(3) [C++, Java] 백준 No.1167 : 트리의 지름

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/390

# C++

#include<iostream>
#include<vector>
#include<utility>
#include<cstring>
#include<queue>

using namespace std;

vector<pair<int, int>> vec[100001]; // 인접리스트
int check[100001];                  // bfs를 위한 check 배열
int dist[100001];                   // 루트로부터의 거리를 저장할 배열
void bfs(int x);

int main()
{
    int n;
    cin >> n;

    // 입력받아서 인접리스트 만들기
    for (int i = 0; i < n; i++){
        //시작정점 입력받기
        int s;
        cin >> s;
        //끝정점 및 가중치를 입력받아 인접리스트에 추가.
        while(true){
            int p; // 정점
            int w; // 가중치
            
            cin >> p;            
            if(p == -1)
                break;
            cin >> w;
            vec[s].push_back(make_pair(p, w));
        }
    }

    // 임의로 설정한 루트 1번으로부터의 거리를 구하기 위한 bfs탐색
    bfs(1);

    // bfs를 통해 루트로 부터 각 점의 거리를 저장하였으므로 가장 먼 점을 찾음
    int farthest_point = 1;
    for(int i = 2; i <= n; i++){
        if (dist[farthest_point] < dist[i])
            farthest_point = i;
    }
    
    memset(check, false, sizeof(check));
    memset(dist, 0, sizeof(dist));

    // 앞에서 찾은 점을 루트로 하여 다시 이로부터의 각 점의 거리를 구함
    bfs(farthest_point);

    // 다시 루트로부터 가장 멀리 떨어진 점을 찾음
    for(int i = 1; i <= n; i++){
        if (dist[farthest_point] < dist[i])
            farthest_point = i;
    }

    // 루트로부터 가장 멀리 떨어진 점의 dist값을 출력
    cout << dist[farthest_point] << "\n";
}

void bfs(int x)
{
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        //cout << currentNode << " ";
        q.pop();
        for(int i = 0; i < vec[currentNode].size() ;i++){
            if(check[vec[currentNode][i].first] == false){
                check[vec[currentNode][i].first] = true;
                q.push(vec[currentNode][i].first);
                dist[vec[currentNode][i].first] =  dist[currentNode] + vec[currentNode][i].second;
            }
        }
    }
}

# Java

import java.util.*;
class Edge {
    public int to;
    public int cost;
    Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}
public class Main {
    public static int[] bfs(int n, List<Edge>[] a, int start) {
        boolean[] check = new boolean[n+1];
        int[] dist = new int[n+1];
        Queue<Integer> q = new LinkedList<Integer>();
        check[start] = true;
        q.add(start);
        while (!q.isEmpty()) {
            int x = q.remove();
            for (Edge e : a[x]) {
                int y = e.to;
                int cost = e.cost;
                if (check[y] == false) {
                    dist[y] = dist[x] + cost;
                    q.add(y);
                    check[y] = true;
                }
            }
        }
        return dist;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Edge>[] a = (List<Edge>[]) new List[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Edge>();
        }
        for (int i=1; i<=n; i++) {
            int x = sc.nextInt();
            while (true) {
                int y = sc.nextInt();
                if (y == -1) break;
                int z = sc.nextInt();
                a[x].add(new Edge(y,z));
            }
        }
        int[] dist = bfs(n, a,1);
        int start = 1;
        for (int i=2; i<=n; i++) {
            if (dist[i] > dist[start]) {
                start = i;
            }
        }
        dist = bfs(n, a, start);
        int ans = dist[1];
        for (int i=2; i<=n; i++) {
            if (ans < dist[i]) {
                ans = dist[i];
            }
        }
        System.out.println(ans);
    }
}