가장 먼 노드

INPUT

노드의 개수 n
간선에 대한 정보가 담긴 2차원 배열 vertex

OUTPUT

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

LOGIC

1번 노드로부터 시작하여, 연결된 노드들을 통과하고, 더이상 연결 된 노드가 없는 곳에 도착했을 때의 길이를 잰다.

해당 길이를 가지는 노드들의 갯수를 반환한다.

어차피 다 탐색해봐야 하니, DFS로 하든 BFS 로 하든 상관 없다. 나는 BFS 로 했다.

우선 노드들이 어떤 노드들과 연결되어 있는 지를 알아야 한다.

ArrayList connections 는 정수를 담는 ArrayList 를 원소로 가진다.

n만큼 connections 의 길이를 늘려 준다. 인덱스를 이용할 때의 편의를 위해 n+1 개 만큼 공간을 할당했다.

vertex 배열을 바탕으로 connections를 채워주게 되면, connections의 i번째에는 i번 노드와 연결되어 있는 노드들의 정보가 담겨 있게 된다.

이 정보들을 기반으로 1부터 시작하여 BFS를 이용한 완전 탐색을 실시하고, 막다른 노드에 도착 시 해당 길이의 정보를 알고 있으면 된다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
    
    	// 초기 세팅
        ArrayList<ArrayList<Integer>> connections = new ArrayList<>();
        for(int i=0;i<=n;i++){
            connections.add(new ArrayList<>());
        }

        for(int[] edges : edge){
            connections.get(edges[0]).add(edges[1]);
            connections.get(edges[1]).add(edges[0]);
        }
        
        // 길이의 최댓값을 저장할 곳
        int max = 0;
        
        // 노드의 방문 여부를 판단. 1번 노드가 방문되면 visited[1] 이 true 가 된다.
        boolean[] visited = new boolean[n+1];
        visited[1]=true;
        
        // 각 노드들의 1번노드와의 최단거리를 담을 배열. distances[2] 는 2번 노드와 1번 노드 사이의 최단 거리이다.
        int[] distances = new int[n+1];
        
        Queue<int[]> queue = new LinkedList<>();
        
        // 노드 1, 길이 0 부터 시작
        queue.add(new int[]{1,0});
        
        while(!queue.isEmpty()){
        	
            // queue 에서 poll 한 정보 (현재 노드, 1번노드와의 거리)
            int[] current = queue.poll();
            int start = current[0];
            int distance =current[1];
            
            // start 번 노드와 연결된 노드들을 찾는다.
            ArrayList<Integer> conn = connections.get(start);
            
            // 모든 연결 노드에 대해 실행한다.
            for(int con : conn){
            
            	// 방문하지 않은 노드 일 시 (최단 거리를 구해야 하기 때문)
                if(!visited[con]){
                	// 방문 처리
                    visited[con]=true;
                    // 지금까지의 지나온 길이 + 1 이 해당 노드의 1번 노드와의 거리가된다.
                    distances[con]=distance+1;
                    // 최대 거리의 값을 갱신한다.
                    max=Math.max(max,distances[con]);
                    // 기존 노드와 연결된 방문하지 않은 새로운 노드를 큐에 추가
                    queue.add(new int[]{con,distance+1});
                }
            }
        }
        
        int answer = 0;
        // 길이가 max 와 같은 노드들의 갯수를 센다.
        for(int i=0;i<distances.length;i++){
            if(distances[i]==max){
                answer++;
            }
        }

        return answer;
    }
}