알고리즘 88 :: 프로그래머스_가장먼노드

import java.util.*;
class Solution {
    
    static boolean[][] map;
    static int cnt = 0;
    static int[] dist;
    static void BFS(int n, int start){
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[1] = 0;
        int max = Integer.MIN_VALUE;
        while(!q.isEmpty()){
            int x = q.poll();
            for(int i=2; i<=n; i++){ 
                if(map[x][i] == true && dist[i] == 0){
                    dist[i] = dist[x] + 1;
                    q.add(i);
                    max = Math.max(dist[i], max);
                }
            }
        }
        for(int i : dist){
            if(i == max){
                cnt +=1;
                
            }
        }//end of for loop
        
    }
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        map = new boolean[n+1][n+1];
        dist = new int[n+1];
       
        
        for(int i=0; i<edge.length; i++){
            int x = edge[i][0];
            int y = edge[i][1];
            map[x][y] = map[y][x] = true;
        }
        //System.out.println(Arrays.deepToString(map));
        BFS(n,1);
        return cnt;
        //노드별 가장 짧은 거리를 저장한다. 
        
    }
}

고정 위치(=1) 에서 시작합니다. dist 란 배열에 고정 위치에서 연결된 노드들 거리를 저장합니다. 가장 긴 길이를 갱신하고 전체 dist 에 저장된 값과 일치한것을 카운트 해주었습니다.

 

배열에 저장된 값을 Integer 로 지정하였는데 테스트케이스 중 메모리가 굉장히 커져서 fail 난 구역이 존재하였습니다. 이에 따라,

Integer 에서 boolean 으로 변경하여 해결하였습니다.