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

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

문제 풀이

(:30)

가장 멀리 떨어진 노드란 "최단경로"로 이동했을 때 간선의 개수가 가장 많은 노드들

• 즉, 이동은 “최단경로로 이동” 하되, 가장 멀리 있는 노드.

문제에서는 “1번 노드로부터 가장 멀리떨어진 노드” 가 몇 개 인지 구하라고 하고 있다.

• 여기서 “경로”는 이동하면서 거친 “간선의 개수”를 말한다. (가중치 그래프는 아님)
• 양방향 그래프다
• 인접노드리스트를 사용하기로 했다 ( 노드 개수가 최대 2만개라서 )

처음에는 특정한 출발점(1번노드)로부터, 모든 노드까지의 최단 거리를 업데이트 해 나가는 디익스트라 기법이 생각났다. 하지만 이 문제는 가중치 그래프가 아니었고, “경로의 길이” 는 “단순히 거쳐간 간선의 개수” 였기 때문에 다른 방법을 쓸 수 있을 것 같았다.

• 디익스트라는 O(n^2logK)
• BFS,DFS 를 사용한다면 depth가 경로의 길이가 된다.-> 따라서, bfs를 사용해서 어떤 노드를 "처음으로" 방문한 거라면, 해당 노드의 최단 길이인 것이다. → 현재 이 문제에선 "가장 멀리 떨어진 노드"를 구해야하므로, bfs를 이용하여 처음으로 방문하면서, 그 depth는 가장 깊은 곳에 위치한 노드들의 개수를 구해야한다 -> element 는 ( depth, 노드번호 ) → element를 저장할 때면, (부모depth+1, 이 노드 번호 )
• 가장 멀리 떨어진 노드의 개수를 세어야하기 때문에, 이를 업데이트 하기 위해 max(현재까지 중, 가장멀리 떨어진 노드까지의 최단 경로 ), maxCnt(가장멀리 떨어진 노드의 개수 )

import java.util.*;
class Solution {
    public boolean[] visit = new boolean[20000];
    public ArrayList<Integer>[] graph = new ArrayList[20000];
    public int max =0, maxCnt =0;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        // init graph 
        for(int i=0;i<n;i++){
            graph[i] = new ArrayList<>();
        }
        // 양방향
        for(int[] e:edge){
            graph[e[0]-1].add(e[1]-1);
            graph[e[1]-1].add(e[0]-1);
        }
        bfs();
        answer = maxCnt;        
        return answer;
    }
    public void bfs(){
        // q 생성
        LinkedList<int[]> q = new LinkedList<>();
        int[] cur = null;
        q.add(new int[]{0,0});
        visit[0] = true;
        while(!q.isEmpty()){
            cur = q.poll();
            // update max 
            if(cur[0] == max){
                maxCnt++;
            }else if( cur[0] > max){
                max = cur[0];
                maxCnt = 1;
            }
            // 현재 노드cur[1] 의 인접 노드 정보들
            for(Integer adj:graph[cur[1]]){
                // 이미 다녀간곳은 패쓰
                if(visit[adj])continue;
                q.add(new int[]{cur[0]+1,adj});
                visit[adj] = true;
            }
        }
    }
}