[백준/1167] 트리의 지름 (java)
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되
www.acmicpc.net
트리의 지름 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율
| 2 초 | 256 MB | 5668 | 2086 | 1574 | 37.149% |
문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.
출력
첫째 줄에 트리의 지름을 출력한다.
예제 입력 1 복사
5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1
예제 출력 1 복사
11
이 경우는 간단하게 생각했다가 피를 봤던 문제이다.
처음 했던 생각은,
각 정점에 대하여 인접리스트와 간선가중치를 저장하는 배열을 만든다.
최대값을 구하는 문제이므로, dfs를 이용하여 각 정점을 다음 값을 찾아 dfs 를 또 요청하고, max 값을 찾으면 될 것 같다.
이렇게 되면, 문제는 각 정점에 대해 매번 dfs가 돌아가면서 max값을 찾는다는 것인데.. 이게 바로 시간 초과가 떴다.
해결방법 : https://dundung.tistory.com/34
백준 1167 트리의지름 Java
정답률 36퍼센트의 트리 문제이다. 트리의 지름을 구하는 문제인데 트리에 존재하는 모든 경로 중 가장 긴 것의 길이를 트리의 지름이라고 한다. BFS/DFS는 그래프에서만 해당되는 탐색 방법인 줄 알았는데 트리..
dundung.tistory.com
효율적인 정답은,
1. 첫번째로 bfs로 조회하여 제일 긴 정점을 찾는다.
2. 긴 정점을 기준으로 bfs로 조회해서 제일 긴 다른 정점을 찾는다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
package bfsdfs;
import java.util.*;
class Edge{ int y; int cost;
public Edge(int y, int cost) { this.y = y; this.cost = cost; } }
public class bj_1167_result {
public static void main(String[] args) { // TODO Auto-generated method stub
Scanner sc = new Scanner(System.in); //LinkedList<Integer> d = new LinkedList<Integer>();
int n = sc.nextInt(); List<Edge>[] d = (List<Edge>[]) new LinkedList[n+1]; int[] dust = new int[n+1];
for (int i=0; i<=n; i++) { d[i] = new LinkedList<Edge>(); }
//입력받기 for( int t=0 ; t<n; t++) { int cur = sc.nextInt();
while (true) { int num = sc.nextInt(); if ( num == -1 ) { break; }
int cost = sc.nextInt(); d[cur].add( new Edge( num, cost ));
} }
//bfs를 이용한 제일 긴 정점 찾기 dust = bfs( d, 1, n );
int start = 0; for ( int i=1; i<dust.length ; i++) { if ( dust[start] < dust[i] ) { start = i; } }
//긴정점을 기준으로 다시 제일 긴 길이를 찾기 dust = bfs( d, start, n);
int max = start; for ( int i=1; i<dust.length ; i++) { if ( dust[max] < dust[i] ) { max = i; } }
System.out.println(dust[max]);
}
public static int[] bfs( List<Edge>[] d, int start , int n ) { boolean[] c = new boolean[n+1];
int[] dust = new int[n+1]; Queue<Integer> q = new LinkedList<Integer>(); q.add(start); c[start] = true;
while(!q.isEmpty()) { int v = q.poll(); c[v] = true;
//List<Edge> list = d[v]; //for( Edge e : list ) { for( Edge e : d[v] ) { int y = e.y; int cost = e.cost; if ( !c[y] ) { q.add(y); dust[y]=dust[v]+cost; } } }
return dust; }
public static int dfs( int cur, ArrayList<Integer>[] d, ArrayList<Integer>[] w , int tmp, boolean[] c ) { c[cur]=true; int rt = 0; int sum = 0;
for( int i = 0 ; i < d[cur].size() ; i++ ) { int next = d[cur].get(i);
if ( c[next] == false ) { c[next] = true; rt = tmp + w[cur].get(i);
sum = dfs( next , d, w, rt, c ); if ( rt < sum ) { rt = sum; } } }
return rt; } }
|
cs |