Life Engineering
[BOJ 1967] 트리의 지름 (Java) 본문
https://www.acmicpc.net/problem/1967
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BOJ_1967 {
static class Edge{
int no;
int weight;
public Edge(int no, int weight) {
this.no = no;
this.weight = weight;
}
}
static ArrayList<ArrayList<Edge>> adjList;
static int N;
static boolean[] check;
static int answer=0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
N=Integer.parseInt(br.readLine());
adjList=new ArrayList<>(N+1);
for (int i=0; i<=N; i++) {
adjList.add(new ArrayList<Edge>());
}
int a, b, c;
for (int i=0; i<N-1; i++) {
st=new StringTokenizer(br.readLine());
a=Integer.parseInt(st.nextToken());
b=Integer.parseInt(st.nextToken());
c=Integer.parseInt(st.nextToken());
adjList.get(a).add(new Edge(b,c));
adjList.get(b).add(new Edge(a,c));
}
for (int i=1; i<=N; i++) {
check=new boolean[N+1];
dfs(i, 0);
}
System.out.println(answer);
}
private static void dfs(int num, int cnt) {
check[num]=true;
if (cnt>answer) answer=cnt;
for (int i=0; i<adjList.get(num).size(); i++) {
Edge neighbor=adjList.get(num).get(i);
if (!check[neighbor.no]) {
dfs(neighbor.no, cnt+neighbor.weight);
}
}
}
}
완전 탐색식으로 풀었다.
1~N번 정점까지 dfs를 돌려 각각 임의의 두 정점 사이의 길이를 구해준다. 그래도 O(N*2) 고, 시간 제한이 2초이므로 가능했지만.. 더 효율적인 풀이가 있었다.
결론적으로 말해서 dfs를 2번만 돌리면 된다.
임의의 정점에서 dfs를 돌렸을 때 최장 거리가 나오는 점은 무조건 지름을 이루는 두 정점 중 하나일 것이다. (이 아이디어를 떠올리는게 어려웠다)
최장 거리가 나오는 점에 대해 dfs를 또 돌려줘서 최장거리가 나오는 경로가 답이 된다.(지름을 이루는 두 정점은 서로에 대해서 최장 거리일 것이므로)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_BOJ_1967 {
static class Edge{
int no;
int weight;
public Edge(int no, int weight) {
this.no = no;
this.weight = weight;
}
}
static ArrayList<ArrayList<Edge>> adjList;
static int N;
static boolean[] check;
static int answer=0;
static int longest;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
N=Integer.parseInt(br.readLine());
adjList=new ArrayList<>(N+1);
for (int i=0; i<=N; i++) {
adjList.add(new ArrayList<Edge>());
}
int a, b, c;
for (int i=0; i<N-1; i++) {
st=new StringTokenizer(br.readLine());
a=Integer.parseInt(st.nextToken());
b=Integer.parseInt(st.nextToken());
c=Integer.parseInt(st.nextToken());
adjList.get(a).add(new Edge(b,c));
adjList.get(b).add(new Edge(a,c));
}
check=new boolean[N+1];
dfs(1,0);
check=new boolean[N+1];
answer=0;
dfs(longest,0);
System.out.println(answer);
}
private static void dfs(int num, int cnt) {
check[num]=true;
if (cnt>answer) {
answer=cnt;
longest=num;
}
for (int i=0; i<adjList.get(num).size(); i++) {
Edge neighbor=adjList.get(num).get(i);
if (!check[neighbor.no]) {
dfs(neighbor.no, cnt+neighbor.weight);
}
}
}
}
시간이 무려 2000ms 에서 200ms 로 줄었다.
'Problem Solving' 카테고리의 다른 글
[BOJ 19238] 스타트 택시 (Java) (0) | 2022.03.23 |
---|---|
[BOJ 1918] 후위 표기식 (Java) (0) | 2022.03.22 |
[BOJ 18111] 마인크래프트 (Java) (0) | 2022.03.22 |
[BOJ 16928] 뱀과 사다리 게임 (Java) (0) | 2022.03.20 |
[BOJ 2565] 전깃줄 (Java) (0) | 2022.03.17 |