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

문제

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

코딩테스트 연습 - 가장 먼 노드

프로그래머스 가장 먼 노드

풀이

bfs로 1번 노드부터 탐색하면서 각 노드 별로 depth를 저장하면 풀 수 있다. 

depth 저장 배열을 정렬시킨 후 max값을 count 한다.

소스코드

import java.util.*;

class Solution {
    int[] depth;
    boolean[] visited;
    ArrayList<Integer>[] nodes;
    public int solution(int n, int[][] edge) {
        // 자료 구조 생성
        depth = new int[n+1];
        nodes = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i = 0; i <= n; i++){
            nodes[i] = new ArrayList<Integer>();
        }
        
        // Input처리
        for(int i = 0; i < edge.length; i++){
            int a = edge[i][0];
            int b = edge[i][1];
            nodes[a].add(b);
            nodes[b].add(a);
        }
        
        bfs();
        
        Arrays.sort(depth);
        int max = depth[n]; // depth의 max값
        int cnt = 1; 
        for(int i = n-1 ; i > 0; i--){
            if(max != depth[i]) break;
            cnt++; // 정렬 되어있는 원소가 max값이 아닌 다른 값이 나올때까지 cnt를 증가시킨다.
        }
 
        return cnt;
    }
    
    public void bfs(){
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(1); // startNode
        que.offer(0); // depth
        visited[1] = true;
        
        while(!que.isEmpty()){
            int node = que.poll();
            int dep = que.poll();
            //각 node의 depth저장
            depth[node] = dep;
            
            for(Integer adj : nodes[node]){
                if(visited[adj]) continue;
                visited[adj] = true;
                que.offer(adj);
                que.offer(dep+1);
            }
        }
    }
}