G1967. 트리의 지름

문제

제출 코드

• 사용 알고리즘 : dfs

모든 leaf노드들에 대하여 dfs를 돌려, 또 다른 leaf노드를 만나면 지나온 길이를 재서 이 중 최대값을 구한다.

처음에 시간초과가 났는데, leaf노드들에 대해서만 dfs를 시행하기 위해 leaf노드들을 ArrayList에 담아두고 코드를 짰었다. contains 메서드를 사용했었는데, leaf노드의 수가 많은 경우 이 부분에서 연산이 길어져 시간초과가 난 듯 했다.

leaf노드들을 따로 담아두지 않고, 인접 노드들을 담아둔 배열의 길이가 1인 노드(=leaf노드)에 대해서만 dfs를 시행하도록 코드를 수정하고 통과했다.

✒️ 기억할 것
-> ArrayList를 사용한 탐색을 시도할 때, 주어진 수에 대한 연산시간을 반드시 고려하기
-> 굳이 필요하다면 map을 사용해보기

package gold;

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 G1967_diameterOfTree {
	static int max = 0;
	static List<Node>[] near;
	static boolean[] visit;

	static class Node{
		int idx, weight;
		Node(int idx, int weight){
			this.idx = idx;
			this.weight = weight;
		}
	}

	static void dfs(int root, int i, int sum) {
		if(near[i].size()==1 && i!=root) {
			max = Math.max(max, sum);
			return;
		}
		for(Node n : near[i]) {
			if(visit[n.idx]) continue;
			visit[n.idx] = true;
			dfs(root, n.idx, sum+n.weight);
		}
	}

	public static void main(String[] args) throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		near = new List[N+1];

		for(int i=0; i<=N; i++) near[i] = new ArrayList<Node>();

		visit = new boolean[N+1];
		for(int i=0; i<N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int parent = Integer.parseInt(st.nextToken());
			int child = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());

			near[parent].add(new Node(child, weight));
			near[child].add(new Node(parent, weight));
		}

		for(int i=1; i<=N; i++) {
			if(near[i].size() > 1) continue;
			visit = new boolean[N+1];
			visit[i] = true;
			dfs(i, i, 0);
		}

		System.out.println(max);
	}

}