[BOJ] 백준 1595번 북쪽나라의 도로 (Java)

#1595 북쪽나라의 도로

난이도 : 골드 3

유형 : 트리의 지름 / dfs 

1595번: 북쪽나라의 도로

▸ 문제

두 도시 사이에 도로를 만드는 일은 매우 비싸다. 때문에 북쪽나라는 특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시간을 이동하는 경로가 유일하도록 도로가 설계되어 있다.

또한 북쪽나라의 모든 도시는 다른 모든 도시로 이동할 수 있다고 한다. 이때, 거리가 가장 먼 두 도시 사이의 거리를 출력하는 것이 당신의 임무이다.

북쪽나라에는 최대 10,000개의 도시가 있을 수 있고, 도시는 1 부터 숫자로 이름이 매겨져 있다.

▸ 입력

입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 양방향으로 통행이 가능하다.

▸ 출력

가장 거리가 먼 두 도시간의 거리를 나타내는 정수 하나를 출력하면 된다.

 

문제 풀이  

트리에서 가장 먼 두 정점 = 트리의 지름 문제이다. 이는 트리의 모든 정점을 브루트포스 탐색을 해야하므로 dfs 또는 bfs 어느 그래프 탐색을 사용해도 상관없다. 그래프 탐색 2번을 돌려서 최대 거리를 구해주면 된다. 이번 문제는 정점 번호는 상관없이 트리의 지름 길이만 구하면 되므로 더 간단하다.

• 트리의 지름이 왜 그래프 탐색 2번으로 구해지는 지에 대한 증명은 여기를 참고

트리의 지름 구하기

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static class Node{
		int to;
		int value;
		
		Node(int to, int value){
			this.to = to;
			this.value = value;
		}
	}
	static List<Node>[] list;
	static boolean[] check;
	static int idx;
	static long max = -1;
	public static void main(String[] args) throws IOException{
		int f = -1;
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));){
			StringTokenizer st;
			String line;
			
			list = new ArrayList[10001];
			for(int i=0; i<10001; i++) {
				list[i] = new ArrayList<>();
			}
			
			while(!(line = br.readLine()).isEmpty()) {
				st = new StringTokenizer(line);
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				f = a;
				list[a].add(new Node(b,v));
				list[b].add(new Node(a,v));
			}
		}catch(Exception e) {}
		
		if(f == -1) {
			System.out.println(0);
			return;
		}
			
		check = new boolean[10001];
		check[1] = true;
		dfs(1,0);
		
		Arrays.fill(check, false);
		check[idx] = true;
		max = -1;
		dfs(idx,0);
		System.out.println(max);
	}
	
	static void dfs(int here, long cost) {
		for(Node nxt : list[here]) {
			if(check[nxt.to]) continue;
			long nxtVal = cost + nxt.value;
			check[nxt.to] = true;
			if(max < nxtVal) {
				idx = nxt.to;
				max = nxtVal;
			}
			dfs(nxt.to, nxtVal);
		}
	}
}