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

풀이방식

main

1. 작은 ArrayList를 담을 큰 ArrayList 생성 및 초기화
2. 작은 ArrayList 초기화
3. 방문 여부를 담을 boolean 배열 생성
4. bfs 호출

bfs

1. 다음에 방문할 노드와 거리를 저장할 Queue 생성
2. Queue에서 한 노드씩 순회
   2-1. 방문한 노드에 따라 최대 깊이 갱신 & 단말노드 개수 갱신
   2-2. 다음에 방문할 Queue 갱신 및 방문 여부 갱신

구현

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

public class NUM49189 {
    public static void main(String[] args) {
        int n = 6;
        int[][] edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0 ; i <= n ; i++) { graph.add(new ArrayList<>()); }
        for(int[] e : edge) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); }

        boolean[] visit = new boolean[n];
        answer = bfs(graph, visit);

        return answer;
    }
    public static int bfs(ArrayList<ArrayList<Integer>> graph, boolean[] visit) {
        int leaf = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        visit[0] = true;

        int maxDepth = 0;
        while(!queue.isEmpty()) {
            int[] distance = queue.poll();
            if (distance[1] > maxDepth) { maxDepth = distance[1]; leaf = 1; }
            else if(distance[1] == maxDepth) { leaf++; }

            for (int i = 0; i < graph.get(distance[0]).size(); i++) {
                int node = graph.get(distance[0]).get(i);
                if (!visit[node-1]) {
                    queue.add(new int[]{node, distance[1] + 1});
                    visit[node-1] = true;
                }
            }
        }

        return leaf;
    }
}

---

*다른 분들의 코드를 참고하여 작성했습니다