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

문제 링크

1167번: 트리의 지름

---

주의사항

• 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

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

 

 

이 문제에 핵심은

1. 트리에 대한 정보를 통해서 두 점 사이에 가장 긴 거리를 출력한다.

2. 각 줄 마지막에는 -1로 표현한다.

3. 두 점 사이의 거리는 주어진다.

 

트리의 특징을 이용해서 2번의 BFS탐색을 통해서 지름을 구하실 수 있습니다.

 

어떤 정점을 시작으로 BFS탐색을 진행하여 가장 먼 정점을 기준으로 다시 BFS탐색을 진행하여 가장 거리가 먼 길이가 트리의 지름이라고 할 수 있습니다.

 

예를들어 

아래와 같은 트리일 때

점 6에서 BFS탐색을 시작하면

가장 먼 거리의 점은 7입니다.

점 7에서 BFS탐색을 다시 시작하면

해당 길이가 트리의 지름이 됩니다.

다른 점을 시작해도 동일한 형태의 지름을 얻을 수 있습니다.

 

2번의 BFS탐색 이후에 트리의 지름을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 트리에 대한 정보를 저장하였습니다.
• BFS로 점 1부터 탐색하도록 bfs함수를 실행하여 가장 긴 점을 구합니다.
• 가장 먼 점을 기준으로 BFS 탐색하도로고 bfs함수를 실행하였습니다.
• BufferedWriter에 가장 먼 점에서 탐색하여 가장 먼 점의 길이가 트리의 지름을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs은 visited[]를 통해 시작정점에서 다른 정점의 거리를 length[]에 저장하였습니다.
• maxGet은 length[]를 통해서 가장 먼 점을 구합니다.

결과 코드

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,max=Integer.MIN_VALUE;
	static ArrayList<ArrayList<tree>> tree = new ArrayList<>();	//트리 관련 정보 리스트
	static int[] length;		//최대 길이 구하는 배열
	static boolean[] visited;	//점 방문 확인 배열
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st;
    	N = Integer.parseInt(br.readLine());
        //트리 관련 리스트 초기화
    	for(int i=0;i<=N;i++) 
    		tree.add(new ArrayList<>());
            //트리 관련 정보 저장
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int point = Integer.parseInt(st.nextToken());
    		while(true) {
    			int next = Integer.parseInt(st.nextToken());
    			if(next==-1)
    				break;
    			int length = Integer.parseInt(st.nextToken());
    			tree.get(point).add(new tree(next,length));
    		}
    	}
        bfs(1);			//아무 점에서 BFS탐색 시작, 저는 1부터 시작했습니다.
        int index = getMax();	//가장 먼 점 구하기
        bfs(index);		//가장 먼 점 기준 BFS 탐색 시작
        max = Integer.MIN_VALUE;
        index = getMax();
    	bw.write(length[index] + "\n");	//지름 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS 탐색 후 가장 먼 점 구하는 함수
    static int getMax() {
    	int index = 0;
    	for(int i=1;i<=N;i++) {
    		if(max<length[i]) {
    			index = i;
    			max = length[i];
    		}
    	}
    	return index;
    }
    //BFS탐색으로 시작 점에서 각 점의 거리 구하는 함수
    static void bfs(int start) {
    	Queue<Integer> queue = new LinkedList<>();
    	length = new int[N+1];
    	visited = new boolean[N+1];
    	visited[start] = true;
    	queue.add(start);
    	while(!queue.isEmpty()) {
    		int cur = queue.poll();
    		for(tree value : tree.get(cur)) {	//현재 점 인접한 점 탐색
    			if(!visited[value.next]&&length[cur] + value.getLength() > length[value.next]) {
    				length[value.next] = length[cur] + value.getLength();
    				visited[value.next] = true;
    				queue.add(value.next);
    			}
    		}
    	}
    	return;
    }
}