문제
트리의 지름
교재 풀이
import java.util.*;
public class P1167_트리의지름 {
static boolean visited[];
static int [] distance;
static ArrayList<Edge_1677>[] A;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 정점의 수
A = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<Edge_1677>();
}
for (int i = 0; i < N; i++) {
int S = sc.nextInt();
while(true)
{
int E = sc.nextInt();
if(E==-1)break;
int V = sc.nextInt();
A[S].add(new Edge_1677(E, V));
}
}
distance = new int[N+1];
visited = new boolean[N+1];
BFS(1);
int Max = 1;
for(int i=2; i<=N; i++) {
if(distance[Max]<distance[i])
Max = i;
}
distance = new int[N+1];
visited = new boolean[N+1];
BFS(Max);
Arrays.sort(distance);
System.out.println(distance[N]);
}
private static void BFS(int index) { // BFS구현
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(index);
visited[index] = true;
while (!queue.isEmpty()) {
int now_node = queue.poll();
for (Edge_1677 i : A[now_node]) {
int e = i.e;
int v = i.value;
if (!visited[e]) {
visited[e] = true;
queue.add(e);
distance[e]=distance[now_node]+v;
}
}
}
}
}
class Edge_1677 {
int e;
int value;
public Edge_1677(int e, int value) {
this.e = e ;
this.value = value;
}
}
내 풀이) 24.6.14에 풀려다 만 흔적
import java.util.*;
import java.io.*;
public class Main
{
static ArrayList<Node>[] a;
static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
a=new ArrayList<Node>[n];
for(int i=0;i<n;i++){
StringTokenizer st=new StringTokenizer(br.readLine());
int k=Integer.parseInt(st.nextToken());
while(k!=-1){
k=
}
}
}
}
public class Node{
int v;
int gajung;
Node(int v, int gajung){
v=this.v;
gajung=this.gajung;
}
}
트리의 지름이란, 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.
트리의 지름을 구하는 프로그램
첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)
둘째 줄부터 V개의 줄에 걸쳐 간선의 정보
정점 번호는 1부터 V까지
하나는 정점번호, 다른 하나는 그 정점까지의 거리
3 1 2 4 3 -1
네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고,
정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.
각 줄의 마지막에는 -1이 입력으로 주어진다.
주어지는 거리는 모두 10,000 이하의 자연수이다.
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
11
접근법
bfs 두 번 사용해서 푸는 문제
인접 리스트, 방문 배열 사용
bfs 의 목적은 가장 거리가 먼 노드를 찾기
즉 제일 깊이가 긴 거
즉 가중치를 탐색하며 계속 더하면서
제일 큰 거를 찾는 거 정도라고 하나
탐색할 때 가중치가 먼 거를 우선해서 탐색하도록 해야 하나
입력은 어떻게
n 입력받고
for n번 반복하는데
자료구조를 노드와 가중치를 동시에 저장할 수 있는 걸로
-1을 만나기 전까지 노드와 가중치 쌍을 입력받고 저장하는 식으로
슈도코드
인접 리스트 a: node를 자료구조로 해서 -> 값과 가중치 동시에
방문 배열: visited
n을 입력받음
for n번 반복해서
while -1이 아닐 때까지
int v
int gajung
a=new node(v, gajung)
지금 당장 생각나는 거는 길이가 긴 걸 먼저 탐색해야 하니까
각 인접 노드별로 gajung을 기준으로 정렬하고
그 후 bfs를 임의로 하나 시작하면 제일 먼 노드를 반환하고
아님 정렬 말고 그냥 bfs 수행할 때 탐색하면서
depth가 1일 때, 2일 때 ... 계속 깊이 가까운 것으로 하는데
각 depth마다 아니다. 상상이 안 됨
for n번 반복해서
collections.sort(a[i])
bfs(아무 노드)
bfs(지름 한 부분)
사용자 정의 자료구조 node
int v
int gajung
설명
- distance 배열을 만들고 사용하면 간단해 지는구나