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

프로그래머스

 

문제 파악

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예시

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

---

접근 방법

1. 인접리스트로 변환
   • 노드가 1번부터 시작하기 때문에 코드 상 0번을 시작하기 위해서 edge에 -1을 해준다.
2. 최단거리로 가장 먼 노드를 찾는 문제기 때문에 BFS 탐색
3. BFS에서 visited 대신 distance 배열을 추가
4. distance 구현 방식
   • 초기 거리는 0에서 시작하므로 첫 번째 방문하는 노드(가장 가까운 노드)는 거리가 1이 됨.
   • 1을 기준으로 그 다음 노드는 +1, 그 하위 노드들도 현재 노드를 기준으로 거리가 1씩 증가

Arrays.fill(distance, -1); // distance를 초기화

q.add(start); // 시작은 0번 노드일테니 0번 노드 추가
distance[start] = 0; // 0번 노드의 distance = 0
        
while(!q.isEmpty()){
	int current = q.remove(); // 현재 노드 저장
	  for (int next : graph.get(current)) { // 다음 노드 예약
	    if (distance[next] == -1) { // 다음 노드의 거리가 -1 -> 방문하지 않았음
	      q.add(next); // 방문 추가
        distance[next] = distance[current] + 1; // 현재 거리에 1을 더해줌
         }
       }
     }
// 완성된 코드는 밑에!!

 

5. 가장 먼 노드 찾기

• 거리를 저장한 배열을 불러옴
• 최대값 max으로 시작 (0으로 초기화)
• 거리가 max보다 클 경우 최대값 갱신
• 최대값이 동률일 경우 카운트 +1
• 새로운 최대값이 나올 수 있기 때문에 최대값이 생길 때마다 1로 초기화

---

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int[][] edges) {
        int[] distance = new int[n];
        // 인접 리스트 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(i, new ArrayList<>()); // 각 노드에 대해 빈 리스트 추가
        }

        // 양방향 간선 추가
        for (int[] edge : edges) {
            int a = edge[0] -1;
            int b = edge[1] -1;

            graph.get(a).add(b); // a -> b 연결
            graph.get(b).add(a); // b -> a 연결 (양방향)
        }

        int answer = 0; // 카운트
        int max = 0; // 최대값
        bfs(graph,distance, 0); // 탐색 시작

        // 최대값을 찾는 로직
        for(int d : distance){
            if(d > max){
                answer = 1;
                max = d;
            }
            else if(d == max){
                answer++;
            }
        }
        return answer;
    }

    void bfs(List<List<Integer>> graph,int[] distance, int start){
        Queue<Integer> q = new LinkedList<>();

        Arrays.fill(distance, -1); // 거리 초기화

        q.add(start); // 0번 노드 추가
        distance[start] = 0; // 0번 노드 초기화

        while(!q.isEmpty()){
            int current = q.remove();
            for (int next : graph.get(current)) {
                if (distance[next] == -1) {
                    q.add(next);
                    distance[next] = distance[current] + 1;
                }
            }
        }

    }
}