문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/49189

구현방법

연결리스트 배열을 통해서 노드 체크

현재 노트를 큐에 추가

count를 추가로 넣어줌으로서 현재 위치가 어디인지 체크합니다.

depth가 cnt 보다 작은 경우 depth값을 cnt로 갱신 해두면서 깊이 체크

visited를 통해서 중복 체크 방지 및 깊이 체크

depth 크기와 각 방문한 노드의 깊이가 같은 경우만 체크해서 answer에 +1을 해준다.

구현알고리즘

BFS 알고리즘

CODE

import java.util.*;

class Solution {

    private ArrayList<Integer>[] adj;
    private int[] visited;
    private int depth = 0;



    public int solution(int n, int[][] edge) {
        int answer = 0;
        adj = new ArrayList[n + 1];
        visited = new int[n + 1];

        for (int idx = 1; idx <= n; idx++)
            adj[idx] = new ArrayList<>();

        for (int idx = 0; idx < edge.length; idx++) {
            int start = edge[idx][0];
            int end = edge[idx][1];

            adj[start].add(end);
            adj[end].add(start);
        }

        bfs(1, 1);

        for (int idx = 1; idx <= n; idx++) {
            if (depth == visited[idx]) answer += 1;
        }

        return answer;
    }

    //핵심 로직
    private void bfs(int start, int count) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        queue.offer(count);
        visited[start] = count;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int cnt = queue.poll();

            //깊이 체크
            if (depth < cnt) depth = cnt;
            for (int idx = 0; idx < adj[cur].size(); idx++) {
                int next = adj[cur].get(idx);

                //0이 아니라는 것으로 방문여부 체크
                if (visited[next] != 0) continue;
                visited[next] = cnt + 1;
                queue.offer(next);
                queue.offer(cnt + 1);
            }
        }
    }

}