[문제] 백준 1967번 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

풀이

 

1. 완전 탐색 => 시간초과

public class BOJ_1967_1 {
	static int N; // 노드의 개수
	static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
	static int[] parents;
	static int max = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(in.readLine()); // 노드 개수

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<int[]>());
		}

		parents = new int[N + 1];
		parents[1] = 1;
		// 노드 간 연결
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			list.get(a).add(new int[] { b, d }); // d : 간선 가중치
			list.get(b).add(new int[] { a, d });
			parents[b] = a;
		}
		// 전체 노드 중 2가지 노드를 뽑는 모든 경우의 수 => 최대값 찾기
		comb(0, new int[2], 1);
		System.out.println(max);

	}
// a노드와 b노드 거리 구하기
	static int distance(int a, int b) {
		int common = sameParent(a, b);
		int dA = 0, dB = 0;
		while (a != common) {
			dA += weight(a, parents[a]);
			a = parents[a];
		}
		while (b != common) {
			dB += weight(b, parents[b]);
			b = parents[b];
		}
		return dA+dB;
	}

	// a: b의 부모노드. a,b노드의 간선 가중치 구하기
	static int weight(int a, int b) {
		int cnt = list.get(a).size();
		for (int i = 0; i < cnt; i++) {
			if (list.get(a).get(i)[0] == b) {
				return list.get(a).get(i)[1];
			}
		}
		return 0;
	}

	// a,b노드의 공통 부모 찾기
	static int sameParent(int a, int b) {
		for(int tmpA = a;tmpA != 1;tmpA = parents[tmpA]) {
			for(int tmpB = b;tmpB!=1;tmpB = parents[tmpB]) {
				if(tmpA==tmpB) {
					return tmpA;
				}
			}
		}
		return 1;
	}

	// 조합
	static void comb(int toSelect, int[] selected, int startIdx) {
		if (toSelect == 2) {
			int d = distance(selected[0], selected[1]);
			max = Math.max(d, max);
			return;
		}
		for (int i = startIdx; i <= N; i++) {
			selected[toSelect] = i;
			comb(toSelect + 1, selected, i + 1);
		}
	}
}

 

2. BFS

public class BOJ_1967_2 {
	static ArrayList<ArrayList<Node>> list = new ArrayList<>();
	static boolean[] visited;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(in.readLine()); // 노드 개수

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<Node>());
		}

		// 노드 간 연결
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			list.get(a).add(new Node(b,w)); // w : 간선 가중치
			list.get(b).add(new Node(a,w));
		}
		
		visited = new boolean[N+1];
		Node farthest= diameter(1);	// root에서 가장 멀리 떨어진 노드 찾기
		
		visited = new boolean[N+1];
		int ans = diameter(farthest.n).weight;	// farthest노드와 가장 멀리 떨어진 노드의 가중치
		
		System.out.println(ans);
		
	}
	//s노드로부터 가장 멀리 떨어진 노드 찾기. s: 시작노드
	static Node diameter(int s) {
		// 반환할 최대 거리와 노드번호
		int max = 0;
		int n = 0;
		
		Queue<Node> q = new LinkedList<>();
		
		q.add(new Node(s,0));
		visited[s] = true;	//시작 노드 방문처리
		//bfs
		while(!q.isEmpty()) {
			Node p = q.poll();
			
			for(int i=0;i<list.get(p.n).size();i++) {	// 해당 노드와 연결된 모든 노드들  순회
				Node node = list.get(p.n).get(i);	// 연결된 노드
				
				if(!visited[node.n]) {	//해당 노드를 방문 안했다면(자식이라면)
					visited[node.n]= true;	//방문 처리
				
					int nw = p.weight + node.weight;	//거리: 시작 노드 ~해당 노드의 가중치 합+ 자식노드의 가중치
					q.add(new Node(node.n, nw));	// 자식노드와 해당노드로까지의 가중치합을 새 노드로 만들어서 큐에 넣음
					
					if(max<nw) {	// 최대값 찾으면
						max= nw;	//max 갱신
						n= node.n;	// 최대 노드 갱신
					}
				}
			}
		}
		
		return new Node(n,max);
	}
}
class Node {
	int n;	//연결된 노드
	int weight;	// 가중치

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

 

3. DFS

 

public class BOJ_1967_3 {
	static ArrayList<ArrayList<Node>> list = new ArrayList<>();
	static boolean[] visited;
	static int N;
	static int farthest, max;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(in.readLine()); // 노드 개수

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<Node>());
		}

		// 노드 간 연결
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			list.get(a).add(new Node(b,w)); // w : 간선 가중치
			list.get(b).add(new Node(a,w));
		}
		if(N==1) {
			System.out.println(0);
			return;
		}
		visited = new boolean[N+1];
		diameter(1,0);	//root에서 가장 먼 노드 찾기
		
		visited = new boolean[N+1];
		diameter(farthest,0);	// root에서 가장 먼노드를 기점으로 가장 거리가 먼 노드 찾기
	
		System.out.println(max);
	}
	//s: 시작노드, d: 누적 가중치
	static void diameter(int s, int d) {
		visited[s] = true;
		
		if(max<d) {	// 최대값,노드 갱신
			max = d;
			farthest = s;
		}
		
		for(Node node: list.get(s)) {	// 시작 노드와 연결된 모든 노드들 중 
			if(!visited[node.n]) {	//자식노드에 대하여
				diameter(node.n,d+node.weight);	// 거리 누적
			}
		}
	}
	static class Node {
		int n;	//연결된 노드
		int weight;	// 가중치

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