[백준] 특정 거리의 도시 찾기

문제

https://www.acmicpc.net/problem/18352

 

 

 

그래프를 표현하는 방법에는 두 가지가 있다.

 

1. 인접 행렬 (Adjacency Matrix)

• N x N 크기의 2차원 배열 사용 (int[][] graph = new int[N][N])
• graph[A][B] = 1 이면 A -> B로 가는 간선이 존재
• 간선이 없으면 0으로 저장

 

2. 인접 리스트 (Adjacency List)

• 리스트 배열 또는 리스트의 리스트 사용 (List<List<Integer>> graph)
• graph[A] 리스트에 B를 저장하면 A -> B로 가는 간선이 존재

 

이 문제는 인접 행렬이 더 적합한데, N이 100,000개만 되어도 100,000 x 100,000 = 10,000,000,000 (100억 개) 크기의 배열이 필요하게 되기 때문이다. 이 정도 크기의 2차원 배열은 메모리 초과가 발생하게 되며, 대부분의 문제에서 N이 클 때 인접 행렬은 사용하지 않는다.

 

또한 모든 노드에 대해 간선이 존재하는지 확인하는 O(N^2) 연산도 필요한데, 이럴 경우에도 불필요한 0이 너무 많아 비효율적이게 된다.

 

인접 리스트를 사용할 경우, 간선 정보만 저장하게 되므로 인접 행렬보다 훨씬 적은 메모리를 사용할 수 있다.

시간 복잡도 또한 간선 개수 M만큼만 탐색하므로 O(N^2)가 아니라 O(N+M)이 되어 탐색 속도도 훨씬 빠르다.

 

 

결론적으로, 인접 행렬은 간선이 많은 밀집 그래프 ( 모든 노드가 연결된 완전 그래프)에 적합하고 인접 리스트는 간선이 적은 희소 그래프 (도로 네트워크)에 적합하다.

 

 

 

 

정답

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, M, K, X;
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        X = sc.nextInt();
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int[] distance = new int[N+1];
        // 그래프 및 최단 거리 테이블 초기화
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
            distance[i] = -1;
        }
        // 모든 도로 정보 입력받기
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            graph.get(A).add(B);
        }

        // 출발 도시까지의 거리는 0으로 설정
        distance[X] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(X);

        while (!queue.isEmpty()) {
            Integer now = queue.poll();
            // 현재 도시에서 이동할 수 있는 모든 도시를 확인
            for (int i = 0; i < graph.get(now).size(); i++) {
                Integer nextNode = graph.get(now).get(i);
                // 아직 방문하지 않은 도시라면
                if (distance[nextNode] == -1) {
                    // 최단 거리 갱신
                    distance[nextNode] = distance[now] + 1;
                    queue.offer(nextNode);
                }
            }
        }

        boolean check = false;
        for (int i = 1; i <= N; i++) {
            if(distance[i] == K) {
                System.out.println(i);
                check = true;
            }
        }
        if(!check) System.out.println(-1);
    }
}