[Programmers] 가장 먼 노드 - JAVA

📚 Problem

가장 먼 노드

• 1번 노드로 부터 가장 멀리 떨어진 노드가 몇개인지 구하기

📝 Solution

Key Idea

• ArrayList<>를 이용해 양방향 그래프를 만듭니다
• Queue에 한층씩 노드를 넣고 해당 노드에 연결된 노드들을 반복문을 돌며 임시큐에 넣습니다
• 한층씩 이동하며 한층에 해당하는 임시큐의 개수를 세면 최종적으로 남는 개수가 답이 됩니다

        while (true) {
            Queue<Integer> temp = new LinkedList<>();

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int node : graph.get(cur)) {
                    if (!visited[node]) {
                        temp.add(node);
                        visited[node] = true;
                    }
                }
            }

            if (temp.isEmpty())
                break;
            queue.addAll(temp);
            cnt = temp.size();
        }

💻 Code

Solution.java

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

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for(int i  = 0; i <= n; i ++)
            graph.add(i, new ArrayList<>());

        for (int[] vertex : edge) {
            graph.get(vertex[0]).add(vertex[1]);
            graph.get(vertex[1]).add(vertex[0]);
        }

        return bfs(n, graph);
    }

    private int bfs(int n, ArrayList<ArrayList<Integer>> graph) {
        int cnt = 0;
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        visited[1] = true;

        while (true) {
            Queue<Integer> temp = new LinkedList<>();

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int node : graph.get(cur)) {
                    if (!visited[node]) {
                        temp.add(node);
                        visited[node] = true;
                    }
                }
            }

            if (temp.isEmpty())
                break;
            queue.addAll(temp);
            cnt = temp.size();
        }

        return cnt;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(6, new int[][]{{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}});
        assertEquals(3, result);
    }
}