Table of contents

프로그래머스 가장 먼 노드

노드의 개수와 간선 정보가 주어졌을 때, 첫 번째 노드로부터 가장 멀리 떨어져 있는 노드의 개수를 구하는 문제이다.

풀이

그래프 탐색에 분류되는 BFS를 이용해서 해결했다.

@Test
public void test() {
    assertThat(solution(6, new int[][]{
        {3, 6},
        {4, 3},
        {3, 2},
        {1, 3},
        {1, 2},
        {2, 4},
        {5, 2},
    })).isEqualTo(3);
}

public int solution(int n, int[][] edge) {
    int answer = 0;

    Graph graph = new Graph(n, edge);
    int max = graph.bfs(1);
    for (int i = 0; i < n; i++) {
        if (graph.nodes[i].distance == max) answer++;
    }

    return answer;
}

class Graph {
    Node[] nodes;
    int maxDistance;

    public Graph(int n, int[][] edge) {
        nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i + 1);
        }
        for (int i = 0; i < edge.length; i++) {
            addEdge(edge[i][0] - 1, edge[i][1] - 1);
        }
    }

    public void addEdge(int a, int b) {
        addEdge(nodes[a], nodes[b]);
    }

    private void addEdge(Node a, Node b) {
        if (!a.adjacents.contains(b)) {
            a.adjacents.add(b);
        }

        if (!b.adjacents.contains(a)) {
            b.adjacents.add(a);
        }
    }

    public int bfs(int n) {
        bfs(nodes[n]);
        return maxDistance;
    }

    private void bfs(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        root.visit = true;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (Node adjecent : node.adjacents) {
                if (!adjecent.visit) {
                    adjecent.distance = node.distance + 1;
                    adjecent.visit = true;
                    maxDistance = Math.max(maxDistance, adjecent.distance);
                    queue.add(adjecent);
                }
            }
        }
    }


    class Node {
        int data;
        int distance;
        boolean visit;
        List<Node> adjacents;

        public Node(int data) {
            this.data = data;
            adjacents = new LinkedList<>();
        }
    }
}

첫 번째 노드를 루트 노드로 시작하여 BFS를 수행한다. 방문하는 노드의 간선의 개수를 갱신하면서 최댓값을 구한다.

BFS에서 간선의 최댓값을 반환하기 때문에 그래프의 모든 노드를 순차 접근하면서 카운트하면 결과를 구할 수 있다. 다른 사람들의 풀이도 조금씩 변형해서 풀었을 뿐, 큐를 이용한 BFS를 베이스로 하기 때문에 구조는 거의 비슷하다.