[프로그래머스/JAVA] 가장 먼 노드

문제 바로가기

 

[문제 설명]

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex		return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]		3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

입출력 예

[코드]

 

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class Solution {     public int solution(int n, int[][] edge) {         int tmp, nn;         int answer = 0;         ArrayList<ArrayList<Integer>> graph = new ArrayList<>();         Queue<Integer> queue = new LinkedList<>();         int[] numbers = new int[n + 1];         for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());         for (int[] ints : edge) {             graph.get(ints[0]).add(ints[1]);             graph.get(ints[1]).add(ints[0]);         }         queue.add(1);         queue.add(1);         int depth = 0;         while (!queue.isEmpty()) {             tmp = queue.poll();             nn = queue.poll();             if (depth < nn) depth = nn;             for (int i = 0; i < graph.get(tmp).size(); i++) {                 int temp = graph.get(tmp).get(i);                 if (numbers[temp] != 0) continue;                 numbers[temp] = nn + 1;                 queue.add(temp);                 queue.add(nn + 1);             }         }         for (int i = 2; i < numbers.length; i++) if (numbers[i] == depth) answer++;         return answer;     } }

[문제 풀이]

노드 정보를 List에 저장하였다.

이때 방향이 없기 때문에 {1,5} 가 주어진다면 1->5, 5->1로 향하는 간선을 모두 저장해야한다.

큐에 시작 노드 1번을 넣고 그 다음으로 넣은 1은 depth인데 문제에서 주어진 가장 많은 간선을 통과한 노드로 가기 위한 간선의 개수라고 보면 된다. while문부터 bfs를 사용하였는데 여기서 특이한 점은 nn이다. nn은 노드를 큐에 넣을 때 depth라고 할 수 있다. 만약 한 번 depth가 삽입되었다면 더이상 넣지 않도록 설정하였는데 그 이유는 depth는 갈수록 커지는데 만약 {1,2}라는 노드 정보를 이용하면 2는 1개의 간선을 가진다. 만약 설정을 하지 않았다면 2는 1개의 간선이 아닌 2개 3개를 넘어 더 많은 간선 개수를 가지게 될 것이다. 마지막으로 depth는 while문을 돌며 최대값으로 갱신되기 때문에 최대값과 동일한 노드를 찾으면 정답을 찾을 수 있다.