[프로그래머스 / Lv.3] - 가장 먼 노드 (Java)

문제

---

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

프로그래머스

 

---

문제 풀이

---

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있다.

 

왜 BFS를 사용해야 할까?

BFS는 그래프 탐색에서 최단 경로를 찾는 데 효율적이다.

• 최단 경로 보장: BFS는 시작 노드에서부터 인접한 노드들을 모두 방문한 후, 그 다음 레벨의 노드들을 방문하기 때문에, 먼저 방문된 노드들은 최단 경로로 방문된 것이다. 따라서 최단 경로를 보장한다.
• 단순하고 직관적: BFS는 큐(Queue)를 사용하여 구현하기 쉽고, 직관적인 탐색 방법이다. 모든 노드를 동일한 깊이로 방문하기 때문에 구현이 간단하다.
• 모든 경로 탐색: BFS는 모든 경로를 탐색하여 최단 경로를 찾기 때문에, 특정 노드까지의 최단 경로를 찾는 데 적합하다.

 

풀이 과정

1. 그래프 초기화: 주어진 간선 정보를 바탕으로 그래프를 초기화한다.
2. BFS를 이용한 최단 거리 계산: BFS를 사용하여 1번 노드로부터 각 노드까지의 최단 거리를 계산한다.
3. 가장 멀리 떨어진 노드 개수 구하기: 최단 거리 배열에서 최대 값을 찾고, 그 최대 값과 같은 거리를 가진 노드의 개수를 센다.

import java.util.*;

class Solution {
    
    private List<Integer>[] graph;
    
    public int solution(int n, int[][] vertex) {
        initGraph(n, vertex);
        int[] distances = bfs(n);
        
        int maxDistance = 0;
        for (int i = 1; i <= n; i++) {
            maxDistance = Math.max(maxDistance, distances[i]);
        }
        
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (distances[i] == maxDistance) {
                count++;
            }
        }
        
        return count;
    }
    
    private int[] bfs(int n) {
        int[] distances = new int[n + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[1] = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : graph[current]) {
                if (distances[neighbor] == Integer.MAX_VALUE) {
                    distances[neighbor] = distances[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }
        
        return distances;
    }
    
    private void initGraph(int n, int[][] edges) {
        graph = new ArrayList[n + 1];
        
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            graph[from].add(to);
            graph[to].add(from);
        }
    }
}