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

❓문제설명

가장 먼 노드

프로그래머스

 

---

🔍문제해석

어떤걸 풀어야 할까?

• 노드와 간선에 대한 정보가 담긴 2차원 배열이 주어지면,노드 1 부터 가장 먼 노드가 몇 개 있는지 구해보자.
• 간선은 양방향이다.

---

🧐문제풀이

• 문제 풀이 구상

간선 정보가 있으니 인접리스트를 생성한다.

노드를 queue에 넣고 하위 노드를 순회하면서, 상위 노드로부터 누적된 거리 + 1을 별도로 저장한다.

그럼 노드별 거리를 저장한 배열에서 가장 큰 수가 가장 먼 거리고, 그 수를 가지고 있는 노드의 개수를 카운트 한 것이 정답이다.

 

• 알고리즘 선택

간선 정보가 있기에 인접리스트를 선택. 

전체 노드간 간선을 탐색해야 가장 먼 거리를 구할 수 있기에 BFS선택..!

 

---

！제출코드

1. 간선을 인접리스트로 만들기

2. 양방향이니 a->b, b->a 2가지 케이스 모두 리스트로 넣어준다.

3. 이동할 노드를 담을 queue 생성. 

4. 각 노드별 이동 거리를 저장할 배열 생성. 방문 체크를 위해 -1로 초기화해준다.

5. 1번 노드부터 출발하니 초기값을 넣어주고 while문 실행.

6. 1부터 현재 노드의 거리  = 이전 노드로부터 누적된 거리 + 1 대입

7. 최초방문한 노드는 queue에 담기(해당 노드의 인접노드들의 거리계산을 위해).

8. 가장 먼 거리 구하기

9. 가장 먼 거리를 갖고있는 노드의 개수를 구하기

import java.util.*;

class Solution {
    
    public static int solution(int n, int[][] edge) {
      
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        for(int i = 0; i<=n; i++) adj.add(new ArrayList<>());
        // (1)
        for(int []e : edge){
            // (2)
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        int answer = bfs(adj);
        return answer;
    }
    public static int bfs(ArrayList<ArrayList<Integer>> adj){
    
        // (3)
        Queue<Integer> queue = new LinkedList<>();
        // (4)
        int[] distance = new int[adj.size()];
        Arrays.fill(distance, -1);

        // (5)
        queue.offer(1);
        distance[1] = 0;
        
        while(!queue.isEmpty()){
        
            int currentNode = queue.poll();
            
            for(int node : adj.get(currentNode)){
            
                if(distance[node] == -1) {
                    // (6)
                    distance[node] = distance[currentNode] + 1;
                    // (7)
                    queue.offer(node);
                }
            }
        }
        
        // (8)
        int MaxDistance = -1;
        for(int d : distance ){
            if(MaxDistance < d) MaxDistance = d;
        }
        // (9)
        int answer = 0;
        for(int d : distance ){
            if(MaxDistance == d) answer++;
        }

        return answer;
    }
}