트리의 지름은 트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것을 말한다. 트리의 지름을 구하시오.
(시간 제한 2초)
입력
1번째 줄에서는 트리의 노드 개수 V(2 ≤ V ≤ 100,000), 2번째 줄부터 V개의 줄에 걸쳐 에지의 정보가 주어진다. 먼저 노드 번호가 주어지고, 그 다음으로 연결된 에지의 정보를 의미하는 정수가 2개씩(연결된 노드 번호, 거리) 주어진다. 거리는 10,000 이하의 자연수다.
예를 들어 2번째 줄에 3 1 2 4 3 -1이 주어질 때 노드 3은 노드 1과 거리가 2인 에지로 연결돼 있고, 노드 4는 거리가 3인 에지로 연결돼 있다는 뜻이다. -1은 더이상 노드가 없으므로 종료한다는 뜻이다.
출력
트리의 지름을 출력한다.
예제 입력
5 // 노드 개수
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1
예제 출력
111단계 - 문제 분석하기
가장 긴 경로를 찾는 방법과 관련된 아이디어가 필요한 문제이다. 아이디어는 다음과 같다.
- 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다.
2단계 - 손으로 풀어 보기
1 그래프를 인접 리스트로 저장한다. (노드, 가중치)를 표현하기 위해 노드는 클래스로 선언한다.
2 임의의 노드에서 BFS를 수행하고 탐색할 때 각 노드의 거리를 배열에 저장한다. 여기에서는 임의의 노드 중 노드 2에서 탐색을 시작하는 경우를 살펴보겠다.
이런 방식으로 노드를 방문하며 거리 배열을 업데이트한다.
3 2에서 얻은 배열에서 임의의 노드와 가장 먼 노드를 찾는다. 그런 다음 그 노드부터 BFS를 다시 수행한다. 현재의 경우 5가 가장 크므로 5부터 다시 BFS를 수행한다.
4 3에서 배열에 저장한 값 중 가장 큰 값을 이 트리의 지름으로 출력한다.
3단계 - sudo코드 작성하기
N(노드 개수) A(그래프 데이터 저장 인접 리스트) // ArrayList<Edge>[] 형태로 선언
visited(방문 기록 저장 배열) distance(거리 저장 배열)
for(N의 개수만큼 반복)
{
A 인접 리스트의 각 ArrayList 초기화
}
for(N의 개수만큼 반복)
{
A 인접 리스트에 그래프 데이터 저장
}
visited 배열 초기화
distance 배열 초기화
임의의 점을 시작으로 BFS 실행
distance 배열에서 가장 큰 값을 지니고 있는 노드를 시작점으로 지정하기
visited 배열 초기화
distance 배열 초기화
새로운 시작점으로 BFS 실행
distance 배열에서 가장 큰 수를 정답으로 출력
BFS {
큐 자료구조에 시작 노드 삽입(add)
visited 배열에 현재 노드 방문 기록
while(큐가 비어 있을 때까지)
{
큐에서 노드 데이터 가져오기(poll)
현재 노드의 연결 노드 중 방문하지 않은 노드로 큐에 데이터 삽입(add)
visited 배열에 방문 기록
현재 노드의 거리 + 에지의 가중치로 방문하지 않은 노드 거리 배열 업데이트
}
}
Edge {
e(목적지 노드), value(에지의 가중치)
}4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Q28 {
static int N;
static ArrayList<Edge>[] A;
static boolean[] visited;
static int[] distance;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<Edge>();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
while (true) {
int e = Integer.parseInt(st.nextToken());
if (e == -1)
break;
int value = Integer.parseInt(st.nextToken());
A[S].add(new Edge(e, value));
}
}
distance = new int[N + 1];
visited = new boolean[N + 1];
BFS(1);
int biggest = 1;
for(int i = 2; i <= N; i++){
if(distance[biggest] < distance[i])
biggest = i;
}
distance = new int[N + 1];
visited = new boolean[N + 1];
BFS(biggest);
Arrays.sort(distance);
System.out.println(distance[N]);
}
private static void BFS(int S){
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(S);
visited[S] = true;
while (!queue.isEmpty()){
int now = queue.poll();
for(Edge i : A[now]){
int e = i.e;
int value = i.value;
if(!visited[e]){
visited[e] = true;
queue.add(e);
distance[e] = distance[now] + value;
}
}
}
}
}
class Edge{
int e;
int value;
public Edge(int e, int value){
this.e = e;
this.value = value;
}
}
- Do it! 알고리즘 코딩테스트 자바 편
