BOJ - 트리의 지름 1167번 (JAVA)

❓ 문제 - 백준 트리의 지름 1167번 - JAVA 풀이법

 

출처 

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

1167번: 트리의 지름

 

 

📝 문제해결법

1. 이 문제는 BFS로 해결했다.

• 트리의 지름을 구하기 위해서는 어느 한 시작점에서 가장 먼곳의 정점을 찾고 그 정점으로 부터 가장 멀리 있는 정점까지의 거리를 구하면 트리의 지름이 나온다.
• 증명의 내용은 (https://blogshine.tistory.com/111)를 참고하면 좋을 것 같습니다 !!!

2. 느낀점

• 다른 풀이를 찾아보니 두 번의 BFS나 DFS를 통해 트리의 지름이 구해진다고 했는데 왜 ???? 그런지는 
• 다들 안 나와 있어서 증명을 직접 찾아보면서 이해했다.
• 이런 논리적인 생각을 할 수 있어서 정말 좋은 문제였던 것 같다.

 

***** 혹시 링크 연결이 문제가 있다면 빠르게 내용 삭제하겠습니다 !!!!!!

 

 

 

💻 소스코드 (JAVA)

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

public class Main {
	public static int n;
	public static class Node {
		int x;
		int dis;
		public Node(int x, int dis) {
			this.x = x;
			this.dis = dis;
		}
	}
	public static ArrayList<ArrayList<Node>> list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		list = new ArrayList<>();
		for(int i=0;i<n+1;i++) {
			list.add(new ArrayList<>());
		}
		
				for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int num = Integer.parseInt(st.nextToken());
			int len = st.countTokens()/2+1;
			for(int j=0;j<len;j++) {
				int idx = Integer.parseInt(st.nextToken());
				if(idx == -1) break;
				int dis = Integer.parseInt(st.nextToken());
				list.get(num).add(new Node(idx, dis));
				list.get(idx).add(new Node(num, dis));
			}
			
		}
		
		int[] arr = bfs(1);
		arr = bfs(arr[1]);
		System.out.println(arr[0]);
		
		
	}
	
	public static int[] bfs(int start) {
		int[] arr = new int[2];
		boolean[] visited = new boolean[n+1];
		Queue<Node> q = new LinkedList<>();
		visited[start] = true;
		q.add(new Node(start, 0));
		int max_dis = 0;
		int max_idx = 0;
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(node.dis > max_dis) {
				max_idx = node.x;
				max_dis = node.dis;
				
			}
			
			for(int i=0;i<list.get(node.x).size();i++) {
				Node conNode = list.get(node.x).get(i);
				if(visited[conNode.x]) continue;
				q.add(new Node(conNode.x, conNode.dis+node.dis));
				visited[conNode.x] = true;
			}
		}
		
		arr[0] = max_dis;
		arr[1] = max_idx;
		return arr;
	}

}