[Java] 프로그래머스 Level 3 : 가장 먼 노드

- 문제설명

- 예시

- 해결과정

• bfs를 통해 너비를 우선으로 탐색했다.
• 너비를 우선으로 탐색하면 현재 탐색하고 있는 너비의 레벨을 체크할 수 있다고 판단했다.
• 여기서 너비의 레벨이란, 루트 노드부터 현재 정점까지 최단 거리로 거쳐온 간선의 수이다.
• 따라서 루트노드의 레벨을 0으로 시작해, 한 단계씩 깊어질 때마다 레벨을 1씩 더해주면 되겠다고 생각했다.
• 가장 깊은 정점까지 갔을 때의 레벨이 루트 노드로부터 현재 정점까지 최단거리로 거쳐온 간선의 수이며, 같은 레벨을 가진 정점이 몇개인지 찾으면 된다!

- 솔루션

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        boolean[] visited = new boolean[n + 1];
        List<Integer>[] node = new ArrayList[n + 1];
        for(int i = 0; i < n + 1; i++) node[i] = new ArrayList<>();
        // 리스트형 배열생성 -> 리스트 초기화

        for(int i = 0; i < edge.length; i++) {
            node[edge[i][0]].add(edge[i][1]);
            node[edge[i][1]].add(edge[i][0]);
        }
        // 인접 리스트 생성

        int[] numOfEdge = bfs(1, node, visited);
        // 정점 별, 거쳐온 간선의 개수를 담은 배열 생성

        int answer = countNumOfMax(numOfEdge);
        // 가장 먼 노드가 몇개인지 세는 과정

        return answer;
    }

    private int[] bfs(int state, List<Integer>[] node, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        q.add(state);
        visited[state] = true;
        int[] numOfEdge = new int[node.length]; // 각 정점마다 거쳐온 간선의 횟수를 담는 배열
        while(!q.isEmpty()) {
            state = q.poll();
            for(int a : node[state]) {
                if(!visited[a]) {
                    numOfEdge[a] = numOfEdge[state] + 1;
                    visited[a] = true;
                    q.add(a);
                }
            }
        }
        return numOfEdge;
    }

    private int countNumOfMax(int[] numOfEdge) {
        int maxValue = 0;
        int count = 1;
        for(int num : numOfEdge) {
            if(num > maxValue) {
                maxValue = num;
                count = 1;
            }
            else if(num == maxValue) {
                count++;
            }
        }
        return count;
    }

}

- 정리

• 인접 리스트로 그래프를 만드는 방식만 사용하지 말고 다양한 방식으로 만들어보자.