[level3] 프로그래머스 - 가장 먼 노드(JAVA)

 

 

[ 풀이 방법 ]

- 그래프의 인접 행렬을 만든다.

 

 

- n번부터 bfs를 돌면서, 단계별 size를 체크한다.

 

- 단계마다 queue를 돌기 전 queue의 size를 answer에 넣어주면, 
   마지막엔 answer에 가장 마지막 단계(즉, 가장 멀리 있는) 노드들의 수가 담긴다.

 

 

 

 

[ 전체 코드 ]

import java.util.*;

class Solution {
    static boolean matrix[][], isVisited[];
	static int answer;

	public int solution(int n, int[][] edge) {
		matrix = new boolean[n + 1][n + 1];
		for (int i = 0; i < edge.length; i++)
			matrix[edge[i][0]][edge[i][1]] = matrix[edge[i][1]][edge[i][0]] = true;

		isVisited = new boolean[n + 1];
		bfs(1);

		return answer;
	}

	static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		isVisited[start] = true;
		queue.offer(start);

		while (!queue.isEmpty()) {
			int size = queue.size();
			answer = size;

			while (--size >= 0) {
				int n = queue.poll();
				for (int i = 1; i < matrix.length; i++) {
					if (!isVisited[i] && matrix[n][i]) {
						isVisited[i] = true;
						queue.offer(i);
					}
				}
			}
		}
	}
}