프로그래머스 - 트리 트리오 중간값

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 트리 트리오 중간값

https://programmers.co.kr/learn/courses/30/lessons/68937

풀이 : BFS 알고리즘을 통해 해당 s위치에서의 각 지점사이의 거리를 계산하여 배열로 리턴한다.
이 문제에서의 최대값이란 서로 멀리 떨어진 지점의 거리(max) 값을 기준으로 max의 값의 갯수가 2개 이상일 때는 중간값이 max로 리턴되고 1개 이하이면 max-1을 리턴한다.

import java.util.*;
class Solution {
    public int solution(int n, int[][] edges) {
        ArrayList <Integer> [] list = new ArrayList[n+1];
	for (int i = 1; i <= n; i++) {
		list[i] = new ArrayList<Integer>();
	}
	for(int [] e : edges) {
		list[e[0]].add(e[1]);
		list[e[1]].add(e[0]);
	}
		
	int [] result = bfs(list, 1, n);
	int s = 1, max = 0, cnt = 0;
	for (int i = 2; i <= n; i++) {
		if(result[i] > result[s]) s = i;
	}
        result = bfs(list, s, n);
	s = 1;
	for (int i = 1; i <= n; i++) {
		if(result[i] > result[s]) s = i;
	}
	for(int i : result) max = Math.max(max, i);
	for(int i : result) if(max == i) cnt++;
	if(cnt >= 2) return max;
	max = 0; cnt = 0;
        result = bfs(list, s, n);
        for(int i : result) max = Math.max(max, i);
        for(int i : result) if(max==i) cnt++;
        if(cnt >= 2) return max;
        return max-1;
    }
    private static int [] bfs(ArrayList<Integer>[] list, int s, int n) {
	boolean [] visit = new boolean [n+1];
	int [] dist = new int [n+1];
	LinkedList<Integer> qu = new LinkedList<Integer>();
	qu.add(s);
	visit[s] = true;
	
	while(!qu.isEmpty()) {
		int num = qu.poll();
		for(int i : list [num]) {
			if(i == num || visit[i]) continue;
			visit[i] = true;
			qu.add(i);
			dist[i] = dist[num] + 1;
		}
	}
	return dist;
}
}