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

접근

이러한 최단거리 문제를 풀 때, 현재 그래프의 데이터를 저장하는 데에는 두 가지 방식이 있다. 간단하게는 이차원 배열을 선언해서 연결된 곳에는 그에 해당하는 거리를, 갈 수 없는 노드라면 -1 혹은 INF값을 저장해놓는 방식이다. 다만 이 경우에는 NxN 으로 모든 노드의 연결 여부를 저장하므로, 간선의 개수가 적은 편이라면 메모리를 낭비하게 된다. 즉, N값이 커지면 메모리 초과가 날 수도 있다는 얘기다. 

 

두 번째로는 이차원 ArrayList를 통해 서로 연결된 노드의 정보만을 저장하는 방식이다. 첫 번째 방식보다 코드 구현 측면에서는 더 복잡하지만, 노드 개수에 비해 간선의 개수가 적다면 이 방식이 더 효율적이다. 나는 두번째 방식으로 풀었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ18352 {
    static class City {
        int num, dist;

        City(int num, int dist){
            this.num = num;
            this.dist = dist;
        }
    }

    static int INF = -1;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        ArrayList<Integer> answer = new ArrayList<>();

        // 입력값 저장
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        int[] dist = new int[n+1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
            dist[i] = INF;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
        }

        // 다익스트라
        dijkstra(dist, x);

        // 거리가 같은 도시의 개수 세기
        for (int i = 1; i <= n; i++) {
            if(dist[i] == k)
                answer.add(i);
        }

        if(answer.size() == 0){
            System.out.println(-1);
        }
        else{
            Collections.sort(answer);
            for (int i = 0, s = answer.size(); i < s; i++) {
                System.out.println(answer.get(i));
            }
        }
    }

    static void dijkstra(int[] dist, int x){
        Queue<City> q = new LinkedList<>();
        
        // 시작 지점 처리
        q.add(new City(x, 0));
        dist[x] = 0;

        while(!q.isEmpty()){
            City cur = q.poll();

            for(int node : graph.get(cur.num)){
                if(dist[node] == INF || dist[node] > cur.dist+1) {
                    dist[node] = cur.dist+1;
                    q.add(new City(node, cur.dist+1));
                }
            }
        }
    }
}