[백준] 1967번:트리의 지름 (Java 자바)

[백준] 1967번:트리의 지름 (Java 자바)

728x90

문제

https://www.acmicpc.net/problem/1967

풀이 및 소스코드

먼저, 트리의 루트로부터 제일 멀리 떨어진 ( 가중치가 제일 큰 ) 노드를 구한다.

예제는 위와 같다.

9번 노드가 가장 멀리 떨어져있음을 알 수 있다.

따라서, 가장 멀리 떨어진 노드부터 그 노드에서 가장 멀리 떨어진 노드가 트리의 지름이라고 할 수 있다.

이때, 자식노드에서 부모노드로 탐색을 해야하기 때문에 양방향 그래프를 만들어주되, dfs 돌릴 때 방문처리를 꼭 해줘야 한다.

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 Main { static int w_max, max_idx; static List[] g; static boolean[] v; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integer.parseInt(br.readLine()); g = new ArrayList[n + 1]; for (int i = 0; i < n+1 ; i++) { g[i] = new ArrayList(); } for (int i = 0; i < n-1; i++) { st = new StringTokenizer(br.readLine()); int p = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); g[p].add(new node(c, w)); g[c].add(new node(p, w)); } // 루트에서 부터 가장 먼 노드 찾기 v = new boolean[n + 1]; v[1] = true; dfs(0, 1); // 루트에서 가장 먼 노드부터 그 노드로부터 가장 먼 노드까지의 길이 구하기 v = new boolean[n + 1]; v[max_idx] = true; dfs(0, max_idx); System.out.println(w_max); } public static void dfs(int w_sum, int p) { // 가중치 합 비교 if (w_sum > w_max) { w_max = w_sum; max_idx = p; } // 하위 혹은 상위 node로 가기 for (node x : g[p]) { if (!v[x.c]) { v[x.c] = true; //방문처리 꼭꼭 dfs(w_sum + x.w, x.c); v[x.c] = false; } } } } class node { int c, w; // 연결된 자식과 가중치 값이 들어감 // 혹은 부모와 가중치 값이 들어감 public node(int c, int w) { super(); this.c = c; this.w = w; } }

반응형

from http://jainn.tistory.com/323 by ccl(A) rewrite - 2021-11-15 15:00:54