728x90
https://www.acmicpc.net/problem/1967
🤔 문제 풀이
그래프 탐색 문제인 트리의 지름 문제이다.
트리의 연결 정보들 중에서 한 정점에서 다른 정점까지의 거리가 가장 긴 것을 찾으면 되는 문제다.
모든 정점에 대한 연결 정보를 저장하기 위해 Node 클래스를 생성하여 정점과 가중치 정보를 저장하고
이를 ArrayList에 저장하였다. 모든 정점 중, 한 start 정점에서 다른 모든 정점을 이동하며
start정점의 최대 길이를 갱신해주고 마지막에 모든 노드의 길이 정보에서 최대 값을 찾는 방식으로 풀었다.
🚨CODE
package ps;
import java.io.*;
import java.util.*;
public class Main {
static boolean[] visit;
static int[] maxLen;
static ArrayList<Node>[] graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
graph = new ArrayList[n+1];
maxLen = new int[n+1];
visit = new boolean[n+1];
for(int i = 1; i<=n; i++) {
graph[i] = new ArrayList<>();
}
StringTokenizer st;
for(int i = 0; i<n-1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, weight));
graph[b].add(new Node(a, weight));
}
for(int i = 1; i<=n; i++) {
dfs(i, i, 0);
Arrays.fill(visit, false);
}
int result = 0;
for(int diameter : maxLen) {
result = Math.max(diameter, result);
}
System.out.println(result);
}
public static void dfs(int startNode, int curNode, int len) {
visit[curNode] = true;
maxLen[startNode] = Math.max(maxLen[startNode], len);
for(Node n : graph[curNode]) {
if(visit[n.value])
continue;
dfs(startNode, n.value, len+n.weight);
}
}
}
class Node{
int value;
int weight;
Node(int value, int weight){
this.value = value;
this.weight = weight;
}
}
728x90
반응형
'코딩테스트' 카테고리의 다른 글
[Silver3-JAVA] 백준 2193 - 이친수 (0) | 2024.03.24 |
---|---|
[Silver2-JAVA] 백준 13565 - 침투 (1) | 2024.03.23 |
[JAVA] 백준 11048 - 이동하기 (0) | 2024.03.19 |
[JAVA] 백준 1238 - 파티 (0) | 2024.03.18 |
[JAVA] 백준 9465 - 스티커 (0) | 2024.03.11 |