[백준] 1967 - 트리의 지름 (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/1967
7. 푼 날짜 : 2023.04.28

1. 사용한 자료구조 & 알고리즘

브루트포스 알고리즘, DFS

2. 사고과정

처음에는 플로이드-워셜 알고리즘으로 풀어보려고 했다. n을 안 보고 그냥 대입했는데, 당연히 안 됐다. n이 10,000이므로 시간복잡도는 최대 O(n^3) 으로 통과 못할 것이다. 시간 복잡도 까지도 안가고 2차원 배열을 생성할 때부터 메모리 초과가 났다. 담부턴 n 보고 풀자...
생각해도 마땅한 풀이법이 안떠올라서 문제 유형을 봤다. dfs를 보는 순간, 어떻게 풀까 생각하다가 모든 노드에서 dfs를 해보기로 했다.

3. 풀이과정

1. 모든 노드에서 dfs 해보기 위해, A 노드에서 연결된 B 노드와 , A노드에서 B 노드로 가는 비용을 저장.
2. 1번 노드부터 마지막 노드까지 dfs를 수행
3. dfs 할 때마다 최대값을 저장

4. 소스코드

import java.util.*;
import java.io.*;



public class Main{
	static ArrayList<Integer[]> graph[];
	static boolean visited[];
	static int max = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		int n=Integer.parseInt(br.readLine());
		visited=new boolean[n+1];
		graph=new ArrayList[n+1];
		for(int i=1;i<graph.length;i++) {
			graph[i]=new ArrayList<>();
		}
		for(int i=0;i<n-1;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			int cost=Integer.parseInt(st.nextToken());
			graph[node1].add(new Integer[] {node2,cost});
			graph[node2].add(new Integer[] {node1,cost});
		}
		for(int i=1;i<graph.length;i++) {
			Arrays.fill(visited,false);	
			dfs(i,0);
		}
		System.out.println(max);

	
	}
	public static void dfs(int node,int sum) {
		visited[node]=true;
		max = Math.max(sum,max);
		
		for(Integer[] temp:graph[node]) {
			int next = temp[0];
			int cost = temp[1];
			if(!visited[next]){
				dfs(next,sum+cost);
			}
		}
		
		
	}
}

5. 결과

진짜 아슬아슬하게 통과했다.
dfs 시간복잡도가 O(ElogV) 이고 , E, V는 10,000이고 , dfs를 n번만큼 하므로 총 O(10000 * 10000 log 10000 ) 으로 대략 O(1,000,000,000) 정도로 생각했다. 결국 3104 ms가 나왔다.

다른 사람 코드를 제출해봤는데 236ms 가 나왔다. 이에 대해서 추가로 공부해 볼 예정이다.

6. 회고

단순히 내 코드에만 봐도 모든 노드에서 수행하는 걸 리프노드에서만 수행했어도 걸리는 시간이 훨씬 줄었을 것 같다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212

7. 추가로 학습한 내용

• <1> 리프 노드를 구하고, 리프 노드에서만 dfs를 수행한 코드 -

import java.util.*;
import java.io.*;



public class Main{
	static ArrayList<Integer[]> graph[];
	static boolean visited[];
	static int max = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		int n=Integer.parseInt(br.readLine());
		visited=new boolean[n+1];
		graph=new ArrayList[n+1];
		for(int i=1;i<graph.length;i++) {
			graph[i]=new ArrayList<>();
		}

		boolean leafNode[]=new boolean[n+1];
		Arrays.fill(leafNode,true);
		for(int i=0;i<n-1;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			int cost=Integer.parseInt(st.nextToken());
			graph[node1].add(new Integer[] {node2,cost});
			graph[node2].add(new Integer[] {node1,cost});
			leafNode[node1] =false;
		}


		for(int i=1;i<leafNode.length;i++) {
			if(leafNode[i]) {
				Arrays.fill(visited,false);	
				dfs(i,0);
			}
		}
		
		System.out.println(max);


	}
	public static void dfs(int node,int sum) {
		visited[node]=true;
		max = Math.max(sum,max);

		for(Integer[] temp:graph[node]) {
			int next = temp[0];
			int cost = temp[1];
			if(!visited[next]){
				dfs(next,sum+cost);
			}
		}


	}
}

• <2> 루트 노드에서 dfs를 수행. (문제에서 root node는 1이라고 주어짐. )
  루트 노드에서 리프 노드로 향하는 가장 가중치가 큰 노드를 찾고, 그 노드에서 dfs를 수행한 코드 (사실상 dfs를 어떤 경우에도 2번만 수행하면 된다. )

import java.util.*;
import java.io.*;



public class Main{
	static ArrayList<Integer[]> graph[];
	static boolean visited[];
	static int max = 0;
	static int findNode = 1 ;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		int n=Integer.parseInt(br.readLine());
		visited=new boolean[n+1];
		graph=new ArrayList[n+1];
		for(int i=1;i<graph.length;i++) {
			graph[i]=new ArrayList<>();
		}

		for(int i=0;i<n-1;i++) {
			st=new StringTokenizer(br.readLine());
			int node1=Integer.parseInt(st.nextToken());
			int node2=Integer.parseInt(st.nextToken());
			int cost=Integer.parseInt(st.nextToken());
			graph[node1].add(new Integer[] {node2,cost});
			graph[node2].add(new Integer[] {node1,cost});
		
		}
		dfs(1,0);
		max=0;
		Arrays.fill(visited,false);
		dfs(findNode,0);
		
		System.out.println(max);


	}
	public static void dfs(int node,int sum) {
		visited[node]=true;
		if(sum>max) {
			max = sum;
			findNode = node;
		}

		for(Integer[] temp:graph[node]) {
			int next = temp[0];
			int cost = temp[1];
			if(!visited[next]){
				dfs(next,sum+cost);
			}
		}


	}
}

<1> 의 결과 : 2096 ms
<2> 의 결과 : 240ms