알고리즘/백준
[백준-1967] 트리의 지름
또도닝
2021. 4. 8. 09:03
이 문제는 백준의 골드 4 레벨인 트리의 지름이라는 문제이다.
이 문제는 처음에 딱 보자마자 가장 긴 점을 어떻게 찾지..? 라는 생각이 들었다.
가중치가 없으면 찾을 수 있을 것 같은데, 가중치를 생각하니까 뭔가 더 어렵게 느껴졌다.
막연하게 dfs로 풀면 될 것 같은데... 라는 생각만 하고 있었는데, 같이 스터디 하는 친구가 로직을 알려주었다.
일단 이 문제는 다른 dfs 문제랑 크게 다르지 않다. 하지만 다른 점이 있다면, dfs를 두번 돌려준다는 것이다.
큰 로직을 보자면,
1) 처음 점을 시작으로 dfs를 돌려준다
2) maxNode를 시작으로 dfs를 돌려준다.
이게 다였다.
maxNode는 dfs를 돌려줄 때 가장 dist가 max값보다 크다면 담아주었다.
코드가 길지 않으니 전체 코드!
import java.util.ArrayList;
import java.util.Scanner;
public class 트리의지름_1967 {
static int N;
static ArrayList<Node>[] list;
static boolean[] visited;
static int max = 0;
static int maxNode = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
list = new ArrayList[N+1];
for(int i=0; i<N+1; i++) {
list[i] = new ArrayList<Node>();
}
for(int i=0; i<N-1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int d = sc.nextInt();
list[a].add(new Node(b,d));
list[b].add(new Node(a,d));
}
visited = new boolean[N+1];
visited[1] = true;
dfs(1,0);
visited = new boolean[N+1];
visited[maxNode] = true;
dfs(maxNode,0);
System.out.println(max);
}
static void dfs(int idx, int dist) {
for(Node n: list[idx]) {
if(!visited[n.idx]) {
visited[n.idx] = true;
dfs(n.idx, dist+n.cnt);
}
}
if(max< dist) {
max = dist;
maxNode = idx;
}
}
static class Node{
int idx;
int cnt;
Node(int idx, int cnt){
this.idx = idx;
this.cnt = cnt;
}
}
}