가장 먼 노드

import java.util.*;
class Solution {
    private static ArrayList<ArrayList<Integer>> listGraph = new ArrayList<ArrayList<Integer>>();
    private static int MAX_VALUE = 20001;
    private static int maxDistance = -1;
 
    // 그래프 추가
    public static void put(int x, int y) {
        listGraph.get(x).add(y);
        listGraph.get(y).add(x);
    }
 
    public static void Dijkstra(int[][] edge, int[] distance, int n, int v) {
        boolean[] check = new boolean[n + 1];
 
        // 거리 값 초기화
        for (int i = 1; i < n + 1; i++) {
            distance[i] = MAX_VALUE;
        }
 
        // 시작노드 값 초기화.
        distance[v] = 0;
        check[v] = true;
 
        // 연결된 노드 거리 값 갱신
        for (int i = 1; i < n + 1; i++) {
            if (!check[i] && listGraph.get(v).contains(i)) {
                distance[i] = 1;
            }
        }
 
        // 다익스트라 알고리즘 반복 횟수는 n-1
        for (int a = 0; a < n - 1; a++) {
            int min = MAX_VALUE;
            int min_index = -1;
 
            // 최소 값 인덱스 찾기
            for (int i = 1; i < n + 1; i++) {
                if (!check[i] && distance[i] != MAX_VALUE) {
                    if (distance[i] < min) {
                        min = distance[i];
                        min_index = i;
                    }
                }
            }
            // 최소 거리 갱신
            check[min_index] = true;
            for (int i = 1; i < n + 1; i++) {
                if (!check[i] && listGraph.get(min_index).contains(i)) {
                    if (distance[i] > distance[min_index] + 1) {
                        distance[i] = distance[min_index] + 1;
                        if (distance[i] > maxDistance)
                            maxDistance = distance[i];
                    }
                }
            }
        }
    }
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int distance[] = new int[n + 1];
 
        // 인접 리스트 생성
        for (int i = 0; i < n + 1; i++) {
            listGraph.add(new ArrayList<Integer>());
        }
        // 인접 리스트 초기화
        for (int i = 0; i < edge.length; i++) {
            put(edge[i][0], edge[i][1]);
        }
        Dijkstra(edge, distance, n, 1);
        for (int i = 1; i < distance.length; i++) {
            if (distance[i] == maxDistance)
                answer++;
        }
        return answer;
    }
}

인접 리스트로 구현한 다익스트라 알고리즘이다.

틀은 이전에 사용했던 인접 행렬로 구현한 다익스트라 알고리즘 코드를 이용하였다.

인접 행렬로 풀이했을 때, 일부 테스트 케이스에서 메모리 초과가 났기 때문에 인접 리스트로 구현하였다.

int 자료형을 최대 20000 * 20000 만큼 할당하기 때문에 초과가 난 것으로 판단된다.

 

인접 행렬로 구현한 코드는 아래와 같다.

class Solution {
    private static int maps[][];
    private static int MAX_VALUE = 20001;
    private static int maxDistance = -1;
 
    public static void Input(int i, int j, int w) {
        if (maps[i][j] > w) {
            maps[i][j] = w;
            maps[j][i] = w;
        }
    }
 
    public static void Dijkstra(int[][] edge, int[] distance, int n, int v) {
        boolean[] check = new boolean[n + 1];
 
        // 거리 값 초기화
        for (int i = 1; i < n + 1; i++) {
            distance[i] = MAX_VALUE;
        }
 
        // 시작노드 값 초기화.
        distance[v] = 0;
        check[v] = true;
 
        // 연결된 노드 거리 값 갱신
        for (int i = 1; i < n + 1; i++) {
            if (!check[i] && maps[v][i] != 0) {
                distance[i] = maps[v][i];
            }
        }
 
        // 다익스트라 알고리즘 반복 횟수는 n-1
        for (int a = 0; a < n - 1; a++) {
            int min = MAX_VALUE;
            int min_index = -1;
 
            // 최소 값 인덱스 찾기
            for (int i = 1; i < n + 1; i++) {
                if (!check[i] && distance[i] != MAX_VALUE) {
                    if (distance[i] < min) {
                        min = distance[i];
                        min_index = i;
                    }
                }
            }
            // 최소 거리 갱신
            check[min_index] = true;
            for (int i = 1; i < n + 1; i++) {
                if (!check[i] && maps[min_index][i] != 0) {
                    if (distance[i] > distance[min_index] + maps[min_index][i]) {
                        distance[i] = distance[min_index] + maps[min_index][i];
                        if (distance[i] > maxDistance)
                            maxDistance = distance[i];
                    }
                }
            }
        }
    }
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int distance[] = new int[n + 1];
        maps = new int[n + 1][n + 1];
        // map 초기화
        for (int i = 1; i < n + 1; i++)
            for (int j = 1; j < n + 1; j++)
                maps[i][j] = MAX_VALUE;
 
        for (int i = 0; i < edge.length; i++)
            Input(edge[i][0], edge[i][1], 1);
 
        Dijkstra(edge, distance, n, 1);
 
        for (int i = 1; i < distance.length; i++) {
            if (distance[i] == maxDistance)
                answer++;
        }
        return answer;
    }
}

정확도는 100%였지만 메모리 초과 제약만 걸린 코드이다.

 

참고 사이트 : https://freestrokes.tistory.com/87

인접 리스트와 인접 행렬의 차이를 기술한 사이트이다.