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

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

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

dfs를 사용했다.

2. 풀이과정

1. 임의의 노드 (여기서는 1번)에서 dfs를 수행한다. 가장 거리가 먼 노드를 찾는다.
2. 그 노드에서 dfs를 수행하면 트리에서 가장 거리가 먼 지점으로 도달할 수 있다. (트리의 지름)

3. 소스코드

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());
		graph=new ArrayList[n+1];
		for(int i=1;i<graph.length;i++)
			graph[i]=new ArrayList<>();
		
		for(int i=1;i<=n;i++) {
			
			String line[]=br.readLine().split(" ");
			int now=Integer.parseInt(line[0]);
			for(int j=1;j<line.length;j+=2) {
				if(j==line.length-1) break;
				int node=Integer.parseInt(line[j]);
				int cost=Integer.parseInt(line[j+1]);
				graph[now].add(new Integer[] {node,cost} );
			}
		}
		
		visited=new boolean[n+1];
		dfs(1,0);
		Arrays.fill(visited,false);
		max = 0;
		
		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);
			}
		}
	}
}

4. 결과

dfs 수행 조건을 잘못 적어서 2번 틀렸다.
틀리고 나서
overflow check를 했는데 최대 10억으로 int 오버플로우는 나지 않을 것으로 예상.
dfs 할 때 수행 구문을 이상하게 적은 것이 원인이었다.

5. 회고

이 문제는 1967번 문제와 거의 유사한데 n이 그 문제보다 10배 크므로
시간 복잡도를 줄이는 데 어떠한 방법을 써야하는지에 대한 고찰을 해야하는 문제였다.

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