링크
https://www.acmicpc.net/problem/1167
문제 설명
정답률 33.978%
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력 예제
- 트리가 입력으로 주어진다.
- 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다.
- 정점 번호는 1부터 V까지 매겨져 있다.
- 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.
- 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.
- 각 줄의 마지막에는 -1이 입력으로 주어진다.
- 주어지는 거리는 모두 10,000 이하의 자연수이다.
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
출력 예제
- 첫째 줄에 트리의 지름을 출력한다.
11
풀이
우선 몰라도 문제는 풀 수 있지만 그래프와 트리, 포레스트의 차이에 대해 알고 가자.
예제를 인접 리스트로 표현하면 다음과 같다.
- 1 (3, 2)
- 2 (4, 4)
- 3 (1, 2) (4, 3)
- 4 (2, 4) (3, 3) (5, 6)
- 5 (4, 6)
그냥 단순히 풀자면 모든 정점을 기준으로 탐색을 하면서 가중치를 더해가면 된다. 하지만 정점의 개수의 최댓값이 이므로 이 경우는 시간 초과가 발생한다.
임의의 두 노드가 가장 긴 경로를 가질 때를 찾아야 하는데 트리에서 임의의 노드에서 가장 긴 경로를 가지는 노드는 문제에서 요구하는 트리의 지름에 해당하는 두 노드 중 하나이다. 그래서 일단 임의의 노드에서 가장 멀리 있는 노드를 찾은 다음 그 노드에서 다시 가장 멀리 있는 노드를 찾고 이 경로의 길이가 답이 된다.
2번 노드부터 탐색을 한다면 각 노드까지 탐색하면서 노드 별 누적 경로는 다음과 같다.
[9, 0, 7, 4, 10]
따라서 가장 긴 경로를 가지는 노드는 5번이 된다.
5번 노드에서 다시 탐색을 진행하면 결과는 다음과 같고
[11, 10, 9, 6, 0]
1번 노드와 5번 노드가 트리의 지름에 해당하는 두 노드가 된다.
코드
//백준
public class Main {
static HashMap<Integer, List<Node>> adjList = new HashMap<>();
static int[] dist;
static boolean[] visited;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int V = Integer.parseInt(br.readLine()); //정점의 수
dist = new int[V + 1]; //누적 경로 저장
visited = new boolean[V + 1];
for (int i = 1; i <= V; i++) {
adjList.put(i, new ArrayList<>());
}
//인접 리스트 저장
for (int i = 1; i <= V; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
while (st.hasMoreTokens()) {
int flag = Integer.parseInt(st.nextToken());
if (flag == -1) {
break;
}
int end = flag;
int weight = Integer.parseInt(st.nextToken());
adjList.get(start).add(new Node(end, weight));
}
}
//첫 번째 노드 찾기
dfs(2, 0);
//dist의 최댓값인 인덱스가 첫 번째 노드
int max = dist[0];
int maxIndex = 0;
for (int i = 1; i <= V; i++) {
if (max < dist[i]) {
max = dist[i];
maxIndex = i;
}
}
dist = new int[V + 1];
//두 번째 노드 찾기
dfs(maxIndex, 0);
Arrays.stream(dist)
.max()
.ifPresent(System.out::println);
}
static void dfs(int node, int weight) {
//누적 경로 갱신
if (dist[node] < weight) {
dist[node] = weight;
}
//인접 노드 탐색
for (Node adjNode : adjList.get(node)) {
//방문 하지 않은 경우
if (!visited[adjNode.end]) {
//현 노드 방문 처리
visited[node] = true;
//경로를 누적하여 재귀 호출
dfs(adjNode.end, weight + adjNode.weight);
//인접 노드 탐색이 끝나면 현 노드는 미방문 처리
visited[node] = false;
}
}
}
static class Node {
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
}
백엔드