BOJ 1167 : 트리의 지름 - https://www.acmicpc.net/problem/1167
우선 입력으로 주어지는 연결관계를 그래프 형태로 나타낸 뒤 가장 긴 거리를 가지는 두 노드를 찾으면 된다.
도착 노드와 거리를 저장할 수 있도록 Edge class를 만들고, 각각 노드 별 ArrayList<Edge>
를 만들어 인접 리스트를 구현해주었다. 예를 들어, 1번 노드와 연결되어 있는 노드들이 nodes[1].add(new Node(idx, weight))
와 같은 식으로 들어간다.
처음에는 bfs로 모든 노드를 시작점으로 bfs를 n번 돌리도록 풀이했는데 시간초과가 났다.. 그래서 찾아보니, 가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2이다. 여기서 가장 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int n;
static int result = 0;
static int max_node = 0;
static ArrayList<Edge>[] nodes;
static class Edge{ // 트리(그래프) 저장용
int end;
int weight;
public Edge(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
static class Node{ // BFS 탐색용
int idx;
int cnt;
public Node(int idx, int cnt) {
this.idx = idx;
this.cnt = cnt;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
nodes = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
nodes[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
String[] inputs = br.readLine().split(" ");
int idx = Integer.parseInt(inputs[0]);
int j = 1;
while(true){
int v_num = Integer.parseInt(inputs[j]);
if(v_num == -1) break;
int weight = Integer.parseInt(inputs[j+1]);
nodes[idx].add(new Edge(v_num, weight));
j += 2;
}
}
bfs(1); // 임의의 노드 1
bfs(max_node); // 임의의 노드 1에서 가장 먼 노드부터 bfs 시작
System.out.println(result);
}
public static void bfs(int start) {
boolean[] visited = new boolean[n + 1];
Queue<Node> q = new LinkedList<>();
q.add(new Node(start, 0));
visited[start] = true;
int max_cnt = 0;
while (!q.isEmpty()) {
Node now = q.poll();
if(now.cnt>max_cnt){
max_cnt = now.cnt; // 가장 멀리 떨어진 노드의 거리
max_node = now.idx; // 가장 멀리 떨어진 노드의 번호
}
for (Edge e : nodes[now.idx]) {
if(!visited[e.end]){
visited[e.end] = true;
q.add(new Node(e.end, now.cnt + e.weight));
}
}
}
result = Math.max(result, max_cnt);
}
}
✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
✔ 난이도 - 🟡 Gold 3