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

[풀이]

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하는 문제로

1번 노드에서 나머지 모든 노드까지의 거리를 구해야 한다.

따라서 bfs 알고리즘을 사용해 시작 노드에서부터 각 노드까지의 거리를 구할 수 있었다.

1번 노드에서부터의 각 노드간 거리 정보를 저장하기 위해 일차원 배열인 len도 선언하였다. 

 

1. 2차원 배열인  graph를 선언하여 각 노드 간의 연결 정보를 저장

2. queue를 선언하여 첫번째 노드와 각 노드간의 거리를 계산

• 처음에 시작 노드인 1번 노드를 queue에 넣어준다.
•  queue가 empty가 될 때 까지 아래 로직을 수행
  • queue에서 최상단에 있는 노드를 pop 꺼내어 해당 노드와 연결된 노드들을 방문
  • 각 노드까지의 거리는 이전 노드까지의 거리 + 1이 된다.
  • 중복 방문을 체크하기 위해 visited 배열도 선언해주었다

위와 같은 방법으로 1번 노드부터 각 노드까지의 거리를 구하였다.

 

3. 각 노드의 거리를 내림차순으로 정렬하면 배열의 첫번째에 가장 멀리 떨어진 노드의 거리가 존재한다.

• maxLen과 동일한 거리들의 개수를 count하여 answer 값에 더해주었다.

[코드]

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] graph = new ArrayList[n+1];

        for(int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }

        int[] len = new int[n+1];

        for(int[] e : edge){
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }
        
        Queue<Integer> q = new LinkedList<>();
        boolean visited[] = new boolean[n+1];
        
        q.add(1);
        visited[1] = true;

        while(!q.isEmpty()){
            int node = q.poll();
            for(int next : graph[node]) {
                if(!visited[next]){
                    len[next] = len[node] + 1;
                    visited[next] = true;
                    q.add(next);
                }
            }
        }

        Arrays.sort(len);
        int maxLen = len[n];
        int answer = 0;

        for(int idx = n ; idx>0 ; idx--) {
            if(len[idx] == maxLen)  answer++;
            else break;
        }


        return answer;
    }
}

 

[문제]

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

프로그래머스