[백준] 트리의 지름(1167)
문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
해설
처음엔 인접리스트와 DFS를 적용해 풀이하려 했으나 시간초과가 발생했다.
모든 정점에서 가장 먼 정점을 찾는 부분이 문제임을 깨닫고,
임의의 정점을 하나 정해 가장 먼 정점을 찾고, 다시 그 정점을 기준으로 가장 먼 정점을 찾도록 구현하였다.
풀이
import java.util.*;
import java.io.*;
public class Main {
static int n;
static List<Edge>[] graph;
static int[] dist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
int v = Integer.parseInt(st.nextToken());
while (true) {
int u = Integer.parseInt(st.nextToken());
if (u == -1)
break;
int cost = Integer.parseInt(st.nextToken());
graph[v].add(new Edge(u, cost));
}
}
dist = new int[n + 1];
bfs(1);
int max = 0, max_idx = 0;
for (int i = 1; i <= n; i++) {
if(max < dist[i]) {
max = dist[i];
max_idx = i;
}
}
Arrays.fill(dist, 0);
bfs(max_idx);
max = 0;
for (int i = 1; i <= n; i++) {
if(max < dist[i]) {
max = dist[i];
}
}
System.out.println(max);
}
public static void bfs(int v) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n + 1];
queue.add(v);
visited[v] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (Edge edge : graph[u]) {
if (!visited[edge.v]) {
visited[edge.v] = true;
queue.add(edge.v);
dist[edge.v] = dist[u] + edge.cost;
}
}
}
}
public static class Edge {
int v, cost;
public Edge(int v, int cost) {
this.v = v;
this.cost = cost;
}
}
}
Author And Source
이 문제에 관하여([백준] 트리의 지름(1167)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gaeunek/backjoon-1167저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)