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

문제

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

프로그래머스

 

---

문제 개요

이 문제는 그래프 탐색 문제로, 1번 노드에서 가장 멀리 떨어진 노드가 몇 개인지를 구하는 문제입니다. 노드 간의 거리는 최단 경로에 포함된 간선의 개수로 측정되며, BFS(너비 우선 탐색) 알고리즘을 활용하여 이를 해결할 수 있습니다.

접근 방법

1. 그래프 표현:
   • 노드 간의 연결 정보는 양방향으로 주어지므로, 인접 리스트를 사용하여 그래프를 표현합니다.
   • 각 노드가 어떤 노드와 연결되는지 리스트 형태로 저장합니다.
2. BFS를 통한 최단 경로 탐색:
   • 최단 경로를 구하는 데 BFS가 적합한 이유는, BFS는 시작 노드에서부터 가까운 노드부터 탐색하므로 먼저 방문한 노드는 항상 최단 경로로 방문된다는 특징이 있습니다.
   • 1번 노드에서부터 BFS를 실행하여 각 노드까지의 거리를 계산하고, 가장 멀리 떨어진 노드들을 찾습니다.
3. 가장 멀리 떨어진 노드 찾기:
   • BFS 탐색 중 현재까지의 최대 거리를 저장하고, 해당 거리와 동일한 거리에 있는 노드의 개수를 세어줍니다.

해결 과정

1. 그래프 초기화:
   • 주어진 노드 수 n과 간선 정보를 기반으로 그래프를 인접 리스트로 표현합니다.
   • graph 리스트에 각 노드의 연결된 다른 노드를 저장합니다.
2. BFS 구현:
   • BFS를 수행하기 위해 큐와 방문 여부를 기록하는 배열(visit)을 사용합니다.
   • 시작 노드인 1번에서부터 BFS를 수행하여 각 노드까지의 거리를 계산하고, 가장 멀리 떨어진 노드의 개수를 세어줍니다.
3. 결과 반환:
   • BFS가 완료되면 가장 멀리 떨어진 노드의 개수를 반환합니다.

그래프 관련 글

import java.util.*;

class Solution {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visit;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        visit = new boolean[n+1];
        
        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 정보를 기반으로 양방향 그래프 생성
        for (int[] arr : edge) {
            graph.get(arr[0]).add(arr[1]);
            graph.get(arr[1]).add(arr[0]);
        }
        
        // BFS 탐색
        answer = bfs();
        
        return answer;
    }
    
    public static int bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0)); // 시작 노드는 1번
        visit[1] = true;
        int max = 0;
        int ans = 0;
        
        // BFS 탐색 시작
        while (!q.isEmpty()) {
            Node cur = q.poll();
            
            // 현재 최대 거리와 같은 경우 카운트 증가
            if (cur.cnt == max) ans++;
            
            // 더 멀리 떨어진 노드가 발견된 경우
            if (cur.cnt > max) {
                ans = 1;
                max = cur.cnt;
            }
            
            // 인접한 노드 탐색
            for (int i = 0; i < graph.get(cur.num).size(); i++) {
                int nextNode = graph.get(cur.num).get(i);
                if (!visit[nextNode]) {
                    q.add(new Node(nextNode, cur.cnt + 1));
                    visit[nextNode] = true;
                }
            }
        }
        return ans;
    }
    
    static class Node {
        int num, cnt;
        public Node(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;            
        }
    }
}