[Programmers] 가장 먼 노드 - 그래프

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

// 가장 먼 노드 - 그래프
public class FarNode {
	private ArrayList<ArrayList<Integer>> list; // 그래프 ; 이중배열이 아닌 이중List로 생성
	private boolean[] visit;
	private int[] d; // 노드 1 부터의 거리를 저장할 배열

	public int solution(int n, int[][] edge) {
		d = new int[n + 1];
		visit = new boolean[n + 1];
		list = new ArrayList<>();
		list.add(new ArrayList<>()); // list의 0번째 인덱스는 빈 List로 채움 (노드의 숫자와 인덱스를 맞추기 위함)
		for (int i = 0; i < n; i++) {
			list.add(new ArrayList<>());
		}
		for (int[] e : edge) { // 그래프 생성
			list.get(e[0]).add(e[1]);
			list.get(e[1]).add(e[0]);
		}
		bfs();
		return count();
	}

	private void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		int s = 1;
		visit[s] = true;
		queue.offer(s);

		while (!queue.isEmpty()) {
			s = queue.poll();
			for (int i = 0; i < list.get(s).size(); i++) {
				int temp = list.get(s).get(i);
				if (!visit[temp]) {
					queue.offer(temp);
					visit[temp] = true;
					d[temp] = d[s] + 1; // 인접되어있는 경우 큐에 넣을 때마다 거리를 하나씩 더해줌
				}
			}
		}
	}

	private int count() { // 가장 먼 노드 개수 카운트
		Arrays.sort(d);
		int max = d[d.length - 1], cnt = 0;
		for (int ele : d) {
			if (max == ele) {
				cnt++;
			}
		}
		return cnt;
	}
}

• BFS를 사용하여 해결
  그래프를 생성할 때, 이중배열보다 이중리스트가 좋음