백준 1167번 : 트리의 지름 - Java

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

1167번: 트리의 지름

1.문제설명

트리의 지름을 구하는 방법은 다음과 같다.

 

아무 노드 A를 택하고, A노드와 가장 멀리있는 노드 B를 찾는다.(BFS or DFS 아무거나 사용해도 된다)

 

그리고 노드 B와 가장 멀리 있는 노드 C를 찾아서

노드 B와 노드 C의 거리를 구하면 그게 트리의 지름이 된다.

 

현재 문제에서 노드간의 거리가 다른데

이 문제는 최단경로를 찾는 문제가 아니므로 다익스트라 알고리즘을 사용할 필요는 없고

BFS로 가장 먼 거리에 있는 노드를 찾아주기만 하면된다.

 

 

2.문제풀이코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
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 ArrayList<Pair>[] adj;
    static int V;
    static Queue<Pair> Q;

    //start node로 부터 가장 멀리 있는 node와 거리를 구하는 함수
    static Pair bfs(int start){
        int end = 0;
        int dist = 0;
        boolean[] visit = new boolean[V+1];
        visit[start] = true;
        Q.add(new Pair(start, 0));

        while(!Q.isEmpty()){
            Pair cur = Q.poll();
            if(cur.dist > dist){
                end = cur.node;
                dist = cur.dist;
            }

            for(int i=0; i<adj[cur.node].size(); i++){
                int nextNode = adj[cur.node].get(i).node;
                int addDist = adj[cur.node].get(i).dist;

                if(!visit[nextNode]){
                    visit[nextNode] = true;
                    Q.add(new Pair(nextNode, cur.dist + addDist));
                }
            }
        }

        return new Pair(end, dist);
    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        adj = new ArrayList[V+1];
        Q = new LinkedList<>();

        for(int i=1; i<=V; i++){
            adj[i] = new ArrayList<>();
        }

        for(int i=1; i<=V; i++){
            st = new StringTokenizer(br.readLine());
            int curNode = Integer.parseInt(st.nextToken());
            int connectNode = Integer.parseInt(st.nextToken());
            
            while(connectNode!=-1){
                int dist = Integer.parseInt(st.nextToken());
                adj[curNode].add(new Pair(connectNode, dist));
                connectNode = Integer.parseInt(st.nextToken());
            }
        }

        Pair start = bfs(1);
        Pair ans = bfs(start.node);
        bw.write(ans.dist+"");
        bw.flush();
        bw.close();
    }
}