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

프로그래머스 가장 먼 노드 문제는 그래프의 한 노드에서 가장 멀리 떨어져 있는 노드의 개수를 구하는 문제다. 난이도는 레벨3이며 그래프 탐색를 통해 해결할 수 있다.

 

프로그래머스 - XX 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- Level 3

 

문제 요약

• n개의 정점으로 이루어진 그래프가 있다.
• 1번 노드에서 가장 먼 노드의 개수는?

 

문제 풀이 과정

• 1번부터 BFS로 돌면서 다른 노드들까지의 최단거리를 구함
• 최대 거리를 갖는 노드의 개수를 구함

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int maxLen = 0;
        
        // 주어진 그래프 정보를 연결 리스트로 변환
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] e : edge) {
            int u = e[0] - 1, v = e[1] - 1; // 인덱스 0번부터로 변환
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        // 1번 (index 0) 노드부터 BFS 수행
        Queue<Vertex> queue = new LinkedList<>();
        int[] dists = new int[n];
        queue.add(new Vertex(0, 0));
        dists[0] = -1;
        
        while(!queue.isEmpty()) {
            Vertex here = queue.poll();

            // 아직 방문하지 않은 인접 노드 방문
            for (Integer nexts : adjList.get(here.node)) {
                if (dists[nexts] == 0) {
                    int nextDist = here.distance + 1;
                    maxLen = Integer.max(maxLen, nextDist);
                    dists[nexts] = nextDist;
                    queue.add(new Vertex(nexts, nextDist));
                }
            }
        }
        
        // 가장 먼 노드 개수 구하기
        for (int dist : dists) {
            if (dist == maxLen) {
                answer++;
            }
        }

        return answer;
    }

    private class Vertex {
        int node;
        int distance;

        public Vertex(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }
}

• 시간복잡도: O(n+E) → BFS 1회 수행(n+E) + 가장 먼 노드 탐색(n)
• 공간복잡도: O(n+E)