[백준 1967번] 트리의 지름 (java)

사용한 방법 : BFS

 

1차 시도 

1번 노드부터 12번 노드까지 차례대로 시작노드로 잡고 BFS를 통해 각각의 길이가 최대가 되는 max값을 구하였다.

1번 노드가 시작점인 경우의 최대값

2번 노드가 시작점인 경우의 최대값

3번 노드가 시작점인 경우의 최대값

...

12번 노드가 시작점인 경우의 최대값

 

그 후, 각각의 최대값들을 또 비교하여 그 중에서 최대가 되는 값이 최종 트리의 지름이 된다.

 

결과 : 메모리 초과

 

2차 시도

트리의 지름을 구하는 간단한 방법을 구글에서 찾아 적용하였다.

 

1. 먼저, 루트 노드를 시작노드로하여 가중치의 합이 가장 큰, 즉 가장 긴 곳의 노드를

   maxDistNode로 지정한다.

2. 그 후, maxDistNode 노드를 다시 시작노드로 하여 가장 긴 곳의 노드까지가 트리의 지름이 된다.

 

결과 : 메모리 초과

 

3차 시도

문제를 보면 노드의 개수는 최대 10000개까지 가능하다. 

2차시도까지 나는 인접행렬을 사용하여 문제를 풀었는데 이 경우 노드의 개수가 10000개라고 하면

10000 x 10000 x 4 바이트 = 400MB가 필요하므로 문제에서 제한된 메모리인 128MB를 훨씬 초과하게 된다는 문제점이 있었다.

 

그래서 인접행렬 대신에 인접리스트를 사용하여 문제를 해결하였다.

2020/01/05 - [개발노트] - 그래프 연결관계

 

최종 코드 :

package num1967;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

public class Main {

	static Vector<Node>[] vector;
	static boolean[] isvisited;
	static int n;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());

		vector = new Vector[n + 1];
		for (int i = 1; i <= n; i++)
			vector[i] = new Vector<>();

		for (int i = 0; i < n - 1; i++) {
			String[] arr = br.readLine().split(" ");
			int A = Integer.parseInt(arr[0]);
			int B = Integer.parseInt(arr[1]);
			int W = Integer.parseInt(arr[2]);

			vector[A].add(new Node(B, W));
			vector[B].add(new Node(A, W));
		}

		isvisited = new boolean[n + 1];
		int maxDistNode = getTreeDiameter(1).n;
		
		isvisited = new boolean[n + 1];
		int res = getTreeDiameter(maxDistNode).weight;

		bw.write(res + "\n");
		bw.flush();

	}

	static Node getTreeDiameter(int s) {

		int max = 0;
		int n = 0;
		Queue<Node> q = new LinkedList<>();

		q.add(new Node(s, 0));
		isvisited[s] = true;

		while (!q.isEmpty()) {

			Node p = q.poll();

			for (int i = 0; i < vector[p.n].size(); i++) {
				Node node = vector[p.n].get(i);

				if (!isvisited[node.n]) {
					int nw = p.weight + node.weight;

					q.add(new Node(node.n, nw));
					if (max < nw) {
						max = nw;
						n = node.n;
					}
					isvisited[node.n] = true;
				}
			}
		}
		return new Node(n, max);

	}

	static class Node {
		int n, weight;

		Node(int n, int weight) {
			this.n = n;
			this.weight = weight;
		}
	}
}