[Java] BOJ 1967번 트리의 지름

[Java] BOJ 1967번 트리의 지름

풀이

1)

트리의 모든점에서 시작하여 리프노드에 갈때까지 가중치를 더해 큰 가중치를 구하는 방법을 사용했습니다.

일단, 통과는 했지만 실행속도가 다른 풀이에 비해 10배 가까이 느려 다른방법을 찾았습니다.

2)

우선 임의의 노드(저는 1번 노드를 사용했습니다)에서 시작해서 가장 긴 지름과 해당 지름을 갖는 도착 노드를 구하고 다시 한번 가장 긴 지름을 갖는 도착노드부터 시작하여 긴 지름을 찾게하였습니다.

자세한 사항은 코드의 주석을 참고해주세요.

코드

1)

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 { public static class Edge { int v, w; public Edge(int v, int w) { super(); this.v = v; this.w = w; } } public static int n, answer; public static boolean[] visited; public static List[] edgeList; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; n = Integer.parseInt(br.readLine()); // 노드는 1부터 시작하므로 visited = new boolean[n + 1]; edgeList = new ArrayList[n + 1]; for (int i = 0; i <= n; ++i) { edgeList[i] = new ArrayList(); } for (int i = 0; i < n - 1; ++i) { st = new StringTokenizer(br.readLine(), " "); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int weight = Integer.parseInt(st.nextToken()); // 방향이 없다는 의미는 // 양방향으로 갈 수 있다는 이야기 edgeList[from].add(new Edge(to, weight)); edgeList[to].add(new Edge(from, weight)); } for (int i = 1; i <= n; ++i) { // 현재점 방문처리 visited[i] = true; // 지름 구하기 getRadius(i, 0); // 다음 검사를 위해 방문처리 해제 visited[i] = false; } System.out.println(answer); } public static void getRadius(int v, int w) { boolean isLeaf = true; // 현재 점과 연결된 모든 점을 방문 for (Edge edge : edgeList[v]) { // 만약 방문한 적이 있는 점이라면 방문 X if (!visited[edge.v]) { // 방문처리 visited[v] = true; // 지름을 구하기 위해 현재까지 구한 지름에 방문하고자하는 다음 점까지의 길이를 더한다. getRadius(edge.v, w + edge.w); // 한 곳도 방문하지 못한경우 즉, 리프노드일 경우를 체크 isLeaf = false; // 다음 검사를 위해 방문처리 해제 visited[v] = false; } } // 만약 방문할 수 있는 정점이 없다면 즉, 리프노드라면 // 최장 길이가 될 수 있으므로 정답을 갱신 if (isLeaf) { answer = (answer < w) ? w : answer; return; } } }

2)

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 { public static class Edge { int v, w; public Edge(int v, int w) { super(); this.v = v; this.w = w; } } public static int n, answer, maxIdx; public static boolean[] visited; public static List[] edgeList; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; n = Integer.parseInt(br.readLine()); // 노드는 1부터 시작하므로 edgeList = new ArrayList[n + 1]; for (int i = 0; i <= n; ++i) { edgeList[i] = new ArrayList(); } for (int i = 0; i < n - 1; ++i) { st = new StringTokenizer(br.readLine(), " "); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); int weight = Integer.parseInt(st.nextToken()); // 방향이 없다는 의미는 // 양방향으로 갈 수 있다는 이야기 edgeList[from].add(new Edge(to, weight)); edgeList[to].add(new Edge(from, weight)); } // 노드는 1부터 시작 visited = new boolean[n + 1]; // 지름 구하기 getRadius(1, 0); // 가장 긴 지름을 갖고있는 노드와 연결된 간선은 // 가중치가 큰 수들로 이루어졌음이 보장되므로 // 해당 노드부터 시작하여 더 큰 지름을 구할 수 있다면 // 그 지름이 가장 긴 지름이 된다. // 노드는 1부터 시작 visited = new boolean[n + 1]; getRadius(maxIdx, 0); System.out.println(answer); } public static void getRadius(int v, int w) { // 기존의 지름보다 큰 지름이라면 if (answer < w) { // 지름 값 갱신 answer = w; // 가장 긴 지름을 갖고있는 노드를 저장 maxIdx = v; } // 방문 처리 visited[v] = true; // 현재 점과 연결된 모든 점을 방문 for (Edge edge : edgeList[v]) { // 만약 방문한 적이 있는 점이라면 방문 X if (!visited[edge.v]) { // 지름을 구하기 위해 현재까지 구한 지름에 방문하고자하는 다음 점까지의 길이를 더한다. getRadius(edge.v, w + edge.w); } } } }

from http://comgong-man.tistory.com/216 by ccl(A) rewrite - 2021-08-09 20:00:21