다희의 코딩 성장일기
[백준] 1967. 트리의 지름 (자바 JAVA) 본문
[ 문제 ] [백준] 1967. 트리의 지름 (자바 JAVA)
문제 링크 : https://www.acmicpc.net/problem/1967
# 접근 방법 및 풀이
- DFS로 풀었다.
- 1~N까지 노드와 연결된 간선정보를 "양방향 인접리스트"로 표현했다.
- 간선에 가중치가 있으므로 연결된 노드 번호와 가중치를 담기 위해 Node라는 클래스를 만들어서 입력을 받았다.
- 1~N까지 모든 노드에 대해 각 노드마다 DFS를 통해 연결된 노드 끝까지 가보며 가중치를 더해간다. 그리고 더한 가중치값 중 가장 큰 max값이 answer가 된다.
- 자세한건 코드참조
# 주의할 점
- 딱히 없음
JAVA 코드
package Gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class bj1967_트리의지름 {
static int N;
static class Node{
int num, len;
public Node(int num, int len) {
this.num = num;
this.len = len;
}
}
static List<Node> list[];
static boolean visit[];
static int ans;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
list = new ArrayList[N+1];
for (int i = 1; i < N+1; i++) {
list[i] = new ArrayList<Node>();
}
for (int i = 0; i < N-1; i++) {
StringTokenizer st = new StringTokenizer(in.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int len = Integer.parseInt(st.nextToken());
list[from].add(new Node(to, len));
list[to].add(new Node(from, len));
}
ans = 0;
for (int i = 1; i <= N; i++) {
visit = new boolean[N+1];
visit[i] = true;
dfs(i, 0);
}
System.out.println(ans);
}
private static void dfs(int num, int dim) {
for (Node node : list[num]) {
if(!visit[node.num]) {
visit[node.num] = true;
dfs(node.num, dim + node.len);
}
}
ans = (ans < dim)? dim : ans;
}
}
REVIEW
'Algorithm > 백준 BOJ' 카테고리의 다른 글
[백준] 2578. 빙고 (자바 JAVA) (0) | 2021.10.06 |
---|---|
[백준] 2608. 로마 숫자 (자바 JAVA) (0) | 2021.09.29 |
[백준] 2800. 괄호 제거 (자바 JAVA) (0) | 2021.09.26 |
[백준] 10451. 순열 사이클 (자바 JAVA) (0) | 2021.09.25 |
[백준] 1254. 펠린드롬 만들기 (자바 JAVA) (0) | 2021.09.23 |
Comments