백준 18352 - 특정 거리의 도시 찾기

Java

18352 번 - 특정 거리의 도시 찾기

문제

접근 방법

한 지점에서 모든 지점까지 최단거리를 찾는다는 문제로, 데이크스트라를 떠올렸다. 하지만 데이크스트라의 시간복잡도 O(V * E)으로 이 문제에는 시간초과가 발생한다.

• V : 정점의 개수
• E : 간선의 개수

코드

import java.util.*;
import java.io.*;
// file input 주석 필수!!
public class Main {
    // x : 출발도시
    // k : 거리 정보
    static int n,m,k,x;
    static List<List<Integer>> list;
    static boolean[] vis;
    static int[] node;
    public static void main(String args[]) throws IOException {
        
        System.setIn(new FileInputStream("C:/Users/taxol/Desktop/DEV/Algo/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        n = stoi(stk.nextToken());
        m = stoi(stk.nextToken());
        k = stoi(stk.nextToken());
        x = stoi(stk.nextToken());

        list = new ArrayList<>();
        
        for(int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        for(int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            list.get(stoi(stk.nextToken())).add(stoi(stk.nextToken()));
        }

        // BFS init
        vis = new boolean[n + 1];
        node = new int[n + 1];

        BFS(x);
        
        List<Integer> ans = new ArrayList();
        for(int i = 1; i <= n; i++) {
            if(node[i] == k) {
                ans.add(i);
            }
        }

        Collections.sort(ans);
        for(int i : ans) {
            System.out.println(i);
        }

        if(ans.isEmpty()) {
            System.out.println(-1);
        }
    }

    static void BFS(int st) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {st, 0});
        vis[st] = true;
        int curN, cost;
        int[] q;
        while(!queue.isEmpty()) {
            q = queue.poll();

            curN = q[0];
            cost = q[1];
            if(cost == k)
                continue;
            for(int next : list.get(curN)) {
                if(!vis[next]) {
                    vis[next] = true;
                    node[next] = cost + 1;
                    queue.add(new int[] {next, cost + 1});
                }
            }
        }

    }
    public static int stoi(String str){
        return Integer.parseInt(str);
    }
}