[프로그래머스, 자바] 가장 먼 노드 (BFS 너비탐색 알고리즘)

프로그래머스 3단계 가장 먼 노드 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/49189?language=java

문제설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 

가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

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

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.

vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

자바코드

           
import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;

class Solution {

    public int solution(int n, int[][] edge) {
        List nodes = new ArrayList<>();
        for (int i = 1; i <= n; i++)
            nodes.add(new Node(i));

        for (int i = 0; i < edge.length; i++) {
            nodes.get(edge[i][0] - 1).addAdjacent(nodes.get(edge[i][1] - 1));
            nodes.get(edge[i][1] - 1).addAdjacent(nodes.get(edge[i][0] - 1));
        }

        boolean[] visited = new boolean[n + 1];
        Queue queue = new ConcurrentLinkedQueue<>();
        visit(visited, nodes.get(0), queue, 0);
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            for (Node adjacent : node.adjacent) {
                if(!visited[adjacent.vertex]) {
                    visit(visited, adjacent, queue, node.count + 1);
                }
            }
        }

        int max = nodes.stream().mapToInt(node -> node.count).max().getAsInt();
        return (int) nodes.stream().filter(node -> node.count == max).count();
    }
    
    public void visit(boolean[] visited, Node node, Queue queue, int count) {
    	visited[node.vertex] = true;
    	node.count = count;
    	queue.add(node);
   
    }

    public class Node {
        private int vertex;
        private List adjacent = new ArrayList<>();
        private int count = Integer.MAX_VALUE;

        public Node(int vertex) {
            this.vertex = vertex;
        }

        public void addAdjacent(Node other) {
            this.adjacent.add(other);
        }
    }
}

문제설명

이 문제는 BFS 너비탐색을 이용하면 풀수 있는 문제이다. 이 문제를 풀면서 BFS는 큐를 이용하고, DFS는 스택과 재귀를 이용하자.

큐가 아닌 재귀를 이용해서도 풀이할 수 있지 않을까? 라는 생각으로 재귀를 이용해봤는데, 많은 시간 낭비를 하였다. 정석을 따르기로 결정했다!

이 문제는 3단계를 통해 풀이가 가능하다.

1단계 : 정점을 가진 노드를 생성하고, 노드의 리스트에 인접 노드를 넣는 작업을 통해 그래프를 그리는 단계

2단계 : BFS를 통해 인접한 노드를 탐색하여, 해당 노드가 기준 노드인 1 노드를 기점으로 간선이 몇개인지 확인하는 단계

3단계 : 간선의 갯수의 최대값을 구하고, 간선의 최대값을 가진 노드들이 몇개인지 카운트하는 단계

2단계가 핵심이다. 특히 2단계에서 기준 노드로부터 해당 노드의 간선의 갯수가 몇개인지 카운트 하는 것이 가장 어려웠다. 그러나 카운트 방법은 생각보다 

간단했다. BFS는 인접 노드를 탐색하는 방식이므로, 인접 노드는 해당 노드의 간선보다 1이 더 많은 셈이다! 

예를들어, 1의 간선의 수는 0이며, 1의 인접한 2의 간선의 수는 1이고, 2의 인접한 5의 간선의 수는 3이다. 

그리고 BFS이기 때문에 방문 유무를 확인하는 boolean 타입의 배열이 반드시 필요하다. 그렇지 않으면 사이클이 존재할 때, 계속해서 무한루프에 빠지는

문제가 발생한다. 

문제를 보자마자 그래프 탐색이다! BFS다! 정답이 바로 나왔는데 시간이 생각보다 많이 소요되었다. 시간이 많이 소요되는 이유는 무엇일까? 생각을 해봤는데

문제를 정확하게 파악하지 않고, 이해하지 않은 상태에서 코드를 구현하려는 급한 마음인것 같다. 이전 코딩 테스트에서도 정확한 풀이법은 고안하지 않는채

구현부터 하려다보니 작성과 수정을 계속 반복하여 시간을 많이 허비했다. 이제는 10분 ~ 15분은 완전히 이해가 되었다해도 정확하게 어떻게 풀것인지

분석을 수행한 후에 푸는 습관을 가져야 겠다! 그래도 결국은 풀었다!!