1167_트리의 지름

사용 알고리즘: bfs

사용 언어: java

 

package week29;

import java.io.*;
import java.util.*;
public class Main_bj_1167_트리의지름 {
	static int v;
	static List<int[]>[] list;

	public static void main(String[] args) throws NumberFormatException, IOException {
		init_트리의지름();
		
		int[] end = find(1);
		int[] answer = find(end[0]);
		
		System.out.println(answer[1]);
	}

	private static int[] find(int startNode) {
		boolean[] visit = new boolean[v+1];
		visit[startNode] = true;
		int endNode = -1;
		int maxLen = 0;
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {startNode, 0});
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			if(maxLen < p[1]) {
				maxLen = p[1];
				endNode = p[0];
			}
			
			for(int[] nxt : list[p[0]]) {
				if(!visit[nxt[0]]) {
					visit[nxt[0]]  = true;
					q.add(new int[] {nxt[0], p[1]+nxt[1]});
				}
			}
		}
		return new int[] {endNode, maxLen};
	}

	private static void init_트리의지름() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		v = Integer.parseInt(br.readLine());
		list = new ArrayList[v+1];
		for(int i=0; i<v+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		for(int i=1; i<v+1; i++) {
			st = new StringTokenizer(br.readLine());
			int node = Integer.parseInt(st.nextToken());
			
			while(true) {
				int nxtNode = Integer.parseInt(st.nextToken());
				if(nxtNode == -1) break;
				int cost = Integer.parseInt(st.nextToken());
				
				list[node].add(new int[] {nxtNode, cost});
			}
		}
	}

}

 

프로그래머스에서도 이런 비슷한 문제를 풀었던 거 같다.

 

임의의 점 A에서 가장 먼 점이 C일 때,

C에서 가장 먼 점 B(A와 B가 같을 수도 있음)를 찾아갈 때, A~C의 경로와 B~C의 경로는 일부 겹치게 된다.

 

그렇기 때문에, 임의의 점(나는 1번 노드로 정함)에서 가장 먼 곳에 있는 점을 구한 후(endNode),

그 점을 다시 시작점으로 놓고 가장 먼 곳의 거리(maxLen)을 구했다.

 

이때 각각을 따로 구하기 위해 bfs를 두 번 구현하는 건 비효율적이라고 생각했다.

어차피 두 번의 bfs 모두 가장 먼 곳의 점과 거리를 알고 있어야 하기 때문이다.

 

그래서 int[]로 리턴 받는 bfs를 만들어서, 각 경우에 필요한 것만 사용하였다.