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

1. 문제

프로그래머스

[문제 요약]

• 1번 노드에서 가장 멀리 떨어진 노드의 갯수 구하기
• n개의 1~n까지 적힌 노드가 있는 그래프
• 가장 멀리 떨어진 노드: 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드

 

2. 생각대로 풀기

최단 경로 문제 -> 가중치가 없다 -> 시작점이 여러개가 아니다 -> BFS

import java.util.*;

class Solution {
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    
    public int solution(int n, int[][] edge) {
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 양방향 간선 추가
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        
        return bfs(n);
    }
    
    private int bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] distance = new int[n + 1];
        Arrays.fill(distance, -1);  // 방문하지 않은 노드는 -1로 초기화
        
        // 시작점 설정
        queue.offer(1);
        distance[1] = 0;
        
        // BFS 탐색
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int next : graph.get(current)) {
                if (distance[next] == -1) {
                    distance[next] = distance[current] + 1;
                    queue.offer(next);
                }
            }
        }
        
        // 최대 거리 찾기
        int maxDistance = 0;
        for (int i = 1; i <= n; i++) {
            maxDistance = Math.max(maxDistance, distance[i]);
        }
        
        // 최대 거리에 있는 노드 개수 세기
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == maxDistance) {
                count++;
            }
        }
        
        return count;
    }
}

1. 간선 정보가 저장된 그래프를 하나 만든다. (양방향이니 둘다 추가)
2. BFS 준비
   1. 방문하지 않은 노드: -1
   2. 시작점: 1
3. BFS 시작
   1. 큐에서 꺼냄
   2. 현재 노드의 모든 인접 노드 확인
   3. 방문하지 않은 인접 노드(-1인 경우)라면
      • 거리 = 현재노드 + 1;
      • 해당 노드를 큐에 추가
   4. 큐가 빌때까지 반복
4. 결과 계산
   1. 최대 거리(가장 큰 값) 찾기
   2. 최대 거리와 같은 값을 가진 노드 개수 세기
   3. 그 개수 반환