[알고리즘] 가장 먼 노드(그래프)

1. 문제

2. 나의 풀이

그래프를 bfs 알고리즘을 이용해서 풀었다. 처음에는 노드의 번호와 1번으로부터 해당 노드까지의 edge 길이를 저장하는 Node 클래스를 선언해서 사용했는데 8,9번쪽에서 메모리 초과 오류가 나서 Integer를 사용하였고 edge 길이의 경우 dist 배열을 하나 선언하여 1번부터 해당 노드까지 이동하는데 드는 비용을 저장했다. 

 

이렇게 변경 후에도 메모리 오류가 나서 graph의 경우는 방문했다 안했다만 저장하면 되므로 int[][] graph에서 boolean[][] graph로 변경하였다.

import java.util.*;

class Solution {

    private static int max = -1;
    private static int maxCount = 0;

    public static int solution(int n, int[][] edge) {

        boolean[][] graph = new boolean[n][n];
        for(int i=0;i<edge.length;i++){
            int n1 = edge[i][0]-1;
            int n2 = edge[i][1]-1;
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }

        bfs(graph, n);

        return maxCount;
    }

    public static void bfs(boolean[][] graph, int n){

        int[] dist = new int[n+1];

        Queue<Integer> q = new LinkedList<>();
        q.add(0);

        while (!q.isEmpty()){
            Integer node = q.poll();

            for(int i=1;i<n;i++){
                if(graph[node][i] == true && dist[i] == 0){ //연결되있고 방문 안했을 경우
                    Integer newNode = i;
                    dist[i] = dist[node]+1;
                    q.add(newNode);
                    if(max < dist[i]){
                        max = dist[i];
                        maxCount = 1;
                    } else if(max == dist[i]){
                        maxCount++;
                    }
                }
            }
        }
    }

}