[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)1967번, 트리의 지름

문제 링크

1967번: 트리의 지름

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

트리 구조 - 위키백과, 우리 모두의 백과사전

 

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

이 문제와 해결과정은 똑같지만 문제 설명만 좀 다른 문제를 풀고 해결과정을 남긴 것을 참고해주시면 감사하겠습니다.

[백준] 단계별로 풀어보기(단계:29, 트리,JAVA)1167번, 트리의 지름

링크의 코드와 아래 코드가 진행되는 과정은 똑같습니다.

 

차이점은 문제를 풀 때마다 동일하게 코드가 작성되지 않아서 약간의 차이점만 존재할 뿐 동일합니다.

 

결과 코드

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

public class Main {
	static class tree{
		int next, length;
		public int getNext() {
			return next;
		}

		public int getLength() {
			return length;
		}

		public tree(int next, int length) {
			this.next = next;
			this.length = length;
		}

	}
	static int N,index=0,max = Integer.MIN_VALUE;
	static ArrayList<ArrayList<tree>> tree = new ArrayList<>();
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
    	for(int i=0;i<=N;i++)
    		tree.add(new ArrayList<>());
    	for(int i=1;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int previous = Integer.parseInt(st.nextToken());
    		int next = Integer.parseInt(st.nextToken());
    		int length = Integer.parseInt(st.nextToken());
    		tree.get(previous).add(new tree(next,length));
    		tree.get(next).add(new tree(previous,length));
    	}
    	bfs(1);
    	bfs(index);
    	bw.write(max + "\n");
    	bw.flush();
    	bw.close();
    	br.close();
    	
    }
    static void bfs(int start) {
    	Queue<Integer> queue = new LinkedList<Integer>();
    	queue.add(start);
    	boolean[] visited = new boolean[N+1];
    	int[] length = new int[N+1];
    	visited[start] = true;
    	while(!queue.isEmpty()) {
    		int cur = queue.poll();
    		for(tree value : tree.get(cur)) {
    			if(!visited[value.getNext()] && length[cur] + value.length > length[value.next]) {
    				visited[value.getNext()] = true;
    				length[value.next] = length[cur] + value.length;
    				queue.add(value.next);
    			}
    		}
    	}
    	maxGet(length);
    	return;
    }
    static void maxGet(int[] length) {
    	for(int i=1;i<=N;i++) {
    		if(length[i] > max) {
    			max = length[i];
    			index = i;
    		}
    	}
    	return;
    }
}