백준
백준 1167번 자바☆
ahlight
2023. 1. 30. 22:20
문제
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
1. DFS로 가능한가?
시간복잡도를 계산하면 V의 범위가 100,000까지기 때문에 최악복잡도는 O(N2) = 약 100억으로 예상된다. 그래서 일반적인 DFS방식으로 풀면 시간초과가 발생한다.
2. 어떻게 접근할 것인가?
한 줄로 요약하면
임의 노드에서 가장 긴경로로 연결돼 있는 노드는 가장 긴 경로(트리의 지름)의 두 노드 중 하나이다.
예제를 그림으로 보도록하자.
그림에서 보듯 임의의 시작점에서 가장 먼 경로의 가장 먼 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.
간단하게 생각해보면 트리라는 자료구조의 특성상 간선으로만 이동을 할 수 있고 중복이 안되기 때문에 가장 긴 경로의 두 노드중 한곳을 반드시 마지막노드로 할 수 밖에 없다.
3. 구현
import java.util.*;
import java.io.*;
public class Main1167 {
static int V;
static Map<Integer, Integer>[] tree;
static boolean[] visited;
static int max;
static int maxNode;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
V = Integer.parseInt(br.readLine());
tree = new HashMap[V+1];
visited = new boolean[V+1];
for (int i=1; i<=V; i++) {
tree[i] = new HashMap<Integer, Integer>();
}
for (int i=1; i<=V; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int idx = Integer.parseInt(st.nextToken());
for (int j=0; j<V; j++) {
int tempKey = Integer.parseInt(st.nextToken());
if (tempKey == -1) {
break;
}
int tempVal = Integer.parseInt(st.nextToken());
tree[idx].put(tempKey, tempVal);
}
}
dfs(1, 0);
visited = new boolean[V+1];
dfs(maxNode, 0);
System.out.println(max);
}
public static void dfs(int node, int distance) {
visited[node] = true;
if (max < distance) {
max = distance;
maxNode = node;
}
Iterator<Integer> tempKey = tree[node].keySet().iterator();
while (tempKey.hasNext()) {
int temp = tempKey.next();
if (!visited[temp]) {
dfs(temp, distance + tree[node].get(temp));
}
}
}
}
정리 : 단순 dfs구현 문제라 생각하고 접근했으나 시간초과에서 많이 헤맸다. 결과를 놓고보면 이해하기 어렵지 않았으나 처음부터 핵심개념을 생각하긴 쉽지않았다. 더 많은 문제를 풀며 경험을 늘려야겠다.