[백준/자바] 1167 트리의 지름

[백준/자바] 1167 트리의 지름 

📌 문제 

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

 

📣 출력

첫째 줄에 트리의 지름을 출력한다.

 

 

 

 

---

 

 

 

💎 문제분석하기

 

문제 해결의 아이디어는 임의의 수에서 거리를 계산했을 때 가장 먼 거리에 있는 노드는 반드시 최대 경로로 설정되는 두 개의 노드 중 하나일 것이라는 것이다.

 

이 개념을 바탕으로 먼저 1개의 노드를 구하고 그 숫자에서부터 다시 최대 거리에 있는 노드를 구하면 해당 두 노드의 거리가 최대 거리가 된다.

 

거리를 측정하기 위해 임시의 배열을 설정하며 이 배열은 최종 답안까지 사용되기 때문에 초기화 해준다. 

 

예제를 토대로 손으로 풀어보면 

임의의 노드 2로부터 시작한다고 했을 때 

 

2 -> 4 -> 3 -> 1 -> 5

 

가는 동안 가장 거리가 먼 5에 10의 숫자가 구해진다 

 

그렇다면 이제 5부터 다시 시작을 해서 가장 큰 값이 나오는 노드를 찾고, 그때의 값이 최대값이 되는 것이다. 

 

 

 

 

 

💡 코드 구현하기

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static boolean[] visited;
	static int[] distance;
	static ArrayList<edge>[] adjacentNodes;

	public static void main(String[] args) {

		/**
		 * 문제 해결의 아이디어는
		 * 임의의 수에서 거리를 계산했을 때 가장 먼 거리에 있는 노드는
		 * 반드시 최대 경로로 설정되는 두 개의 노드 중 하나일 것이라는 것이다
		 * <p>
		 * 이 개념을 바탕으로 먼저 1개의 노드를 구하고
		 * 그 숫자에서부터 다시 최대 거리에 있는 노드를 구하면
		 * 해당 두 노드의 거리가 최대 거리가 된다
		 * <p>
		 * 거리를 측정하기 위해 임시의 배열을 설정한다
		 */

		Scanner scanner = new Scanner(System.in);
		int numberOfNodes = scanner.nextInt();                    // 입력 받는 노드의 개수

		setUptAdjacentNodesStorage(numberOfNodes);
		saveNodeMap(scanner, numberOfNodes);
		bfs(1);        // 임의의 점 (1로 세팅)에서 bfs 탐색
		bfs(findMaxDistanceNode(numberOfNodes));        // 가장 큰 값을 지니는 노드를 찾고 해당 노드를 시작점으로 지정

		System.out.println(Arrays.stream(distance).max().getAsInt());    // 최대값을 출력
	}

	private static int findMaxDistanceNode(int numberOfNodes) {
		int Max = 1;

		for (int i = 2; i <= numberOfNodes; i++) {
			if (distance[Max] < distance[i])
				Max = i;
		}

		initializeCalculationModules(numberOfNodes);
		return Max;
	}

	private static void initializeCalculationModules(int numberOfNodes) {
		distance = new int[numberOfNodes + 1];
		visited = new boolean[numberOfNodes + 1];
	}

	private static void saveNodeMap(Scanner sc, int numberOfNodes) {
		for (int i = 0; i < numberOfNodes; i++) {
			int thisNode = sc.nextInt();
			while (true) {
				int otherNode = sc.nextInt();
				if (otherNode == -1) break;
				int cost = sc.nextInt();
				adjacentNodes[thisNode].add(new edge(otherNode, cost));
			}
		}
		initializeCalculationModules(numberOfNodes);
	}

	private static void setUptAdjacentNodesStorage(int N) {
		adjacentNodes = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			adjacentNodes[i] = new ArrayList<>();
		}
	}

	private static void bfs(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		visited[node] = true;

		while (!queue.isEmpty()) {
			int now_node = queue.poll();

			for (edge edge : adjacentNodes[now_node]) {
				int otherNode = edge.edge;
				int cost = edge.value;

				if (!visited[otherNode]) {
					visited[otherNode] = true;
					queue.add(otherNode);
					Main.distance[otherNode] = Main.distance[now_node] + cost;    // 거리 배열 업데이트 로직
				}
			}
		}
	}
}


class edge {
	int edge;
	int value;

	public edge(int edge, int cost) {
		this.edge = edge;
		this.value = cost;
	}
}

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편