[프로그래머스] Lv3. 가장 먼 노드 - 자바(JAVA)

문제 설명

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

 

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

 

제한사항

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

---

문제 파악

• 주어진 그래프에서 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.
• 모든 간선은 양방향이며, 그래프는 하나의 연결 요소로 이루어져 있다.

 

접근 방법

• BFS를 사용한다.
• 간선 정보를 이용해 인접 리스트를 만든다.
• BFS는 시작 노드에서 가까운 노드부터 차례로 방문하기 때문에, 각 노드까지의 최단 거리를 쉽게 구할 수 있다.
• 모든 노드에 대해 최단 거리를 계산한 뒤, 가장 멀리 떨어진 거리를 가진 노드의 개수를 센다.

 

코드 구현

import java.util.*;

public class Solution {

    public int solution(int n, int[][] vertex) {
        // 인접 리스트 만들기
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보로 연결하기
        for (int[] edge : vertex) {
            int a = edge[0];
            int b = edge[1];
            graph.get(a).add(b);
            graph.get(b).add(a); // 양방향이므로 양쪽에 모두 추가
        }

        // 1번 노드부터 BFS 시작
        return bfs(n, graph, 1);
    }
    
    public int bfs(int n, List<List<Integer>> graph, int startVertex) {
        // BFS를 사용하여 가장 멀리 떨어진 노드 구하기
        Queue<Integer> queue = new LinkedList<>();
        int[] distance = new int[n + 1]; // 노드 번호는 1부터 n까지인데 0번은 비워두므로 n+1 크기로 선언
        Arrays.fill(distance, -1); // 방문 안한 노드 초기 거리 -1로 설정 (0으로 하면 헷갈리므로)
        queue.add(startVertex);
        distance[startVertex] = 0; // 시작 노드는 0으로 설정
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int next : vertex.get(current)) {
                if (distance[next] == -1) { // 아직 방문하지 않은 노드라면
                    queue.add(next);
                    distance[next] = distance[current] + 1; // 현재 노드로부터 1만큼 멀어진 거리
                }
            }
        }

        // 가장 멀리 떨어진 거리 계산
        int maxDistance = 0;
        for (int dist : distance) {
            if (dist > maxDistance) {
                maxDistance = dist;
            }
        }

        // 가장 멀리 떨어진 노드의 개수 세기
        int count = 0;
        for (int dist : distance) {
            if (dist == maxDistance) {
                count++;
            }
        }

        return count;
    }
}

• distance 배열을 -1로 초기화해 방문 여부를 체크하고, 최단 거리를 저장한다.
• BFS를 돌면서 거리를 하나씩 늘린다.
• 가장 큰 거리를 가진 노드의 개수를 세어 반환한다.

 

다른 풀이 (정답 코드)

1) BFS - List

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
	    //✅ 주어진 엣지 데이터를 사용하기 쉽게 가공한다.
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        
        boolean[] visited = new boolean[n+1];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{ 1, 0 });
        visited[1] = true;
        
        //✅ BFS 탐색을 수행하며 정답을 업데이트한다.
        int maxDist = 0, count = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.remove();
          
            if (maxDist < cur[1]) {
                maxDist = cur[1];
                count = 1;
            } else if (maxDist == cur[1]) {
                count++;
            }
            
            for (int next : graph.get(cur[0])) {
                if (visited[next]) continue;
                visited[next] = true;
                queue.add(new int[]{ next, cur[1] + 1 });
            }
        }
        
        return count;
    }
}

• queue에 [노드, 거리] 형태로 저장하여 매번 거리를 함께 관리한다.
• 최대 거리 갱신 시 바로 count를 초기화하거나 증가시켜서 더 빠르게 계산한다.

 

2) BFS - Set 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int maxDepth = 0;
        int answer = 0;
        HashMap<Integer,Set<Integer>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashSet<>());
        }
        for (int[] e : edge){
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        ArrayDeque<Pair> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        
        queue.add(new Pair(1, 1));
        visited[1] = true;
        
        while(!queue.isEmpty()){
            Pair cur = queue.remove();
            int node = cur.node, depth = cur.depth;
            if (depth > maxDepth){
                maxDepth = depth;
                answer = 0;
            }
            answer++;
            for (int neighbor : graph.get(node)){
                if (!visited[neighbor]){
                    queue.add(new Pair(neighbor, depth+1));
                    visited[neighbor] = true;
                }
            }
        }
        
        return answer;
    }
    
    class Pair{
        int node;
        int depth;
        public Pair(int node, int depth){
            this.node = node;
            this.depth = depth;
        }
    }
}

• depth를 별도로 관리하는 클래스를 만들어 사용한다.
• 최대 depth를 갱신하면서 answer를 다시 세는 방식

 

배운 점

• BFS 구현 방법을 알게 되었다.
• 노드 번호가 1부터 n까지인데 배열은 0번 공간이 생기므로 n+1개로 만든다.
• distance 배열 초기화를 0으로 하면 거리가 0인 경우와 구분이 어려우므로 -1로 설정한다.
• 간선 정보(edges)가 주어질 때, 이를 인접 리스트로 변환해서 그래프로 다룰 수 있다.

 

개념 정리

- List와 Set의 차이

	List	Set
중복 허용	O	X
순서 유지	O	X (LinkedHashSet은 유지)
인덱스 접근	O (list.get(0) )	X
탐색 속도	느림 (O(n))	빠름 (HashSet 기준 O(1))
주 사용 목적	순서대로 여러 데이터 관리	고유한 데이터 관리, 빠른 탐색

 

* Set를 사용하면 중복 간선을 자동으로 방지 가능하고 빠른 탐색 가능