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

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

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

풀이

사용한 알고리즘 : 데익스트라(Dijkstra)

 

풀이전략

전형적인 데익스트라 알고리즘을 사용한 최단거리 문제이다.

 

다만 계속해서 시간초과가 발생해서 골머리였는데, 이유는 ArrayList가 아닌 LinkedList 사용 때문이었다.

 

                                           ArrayList     /      LinkedList

검색 최대 시간 복잡도 ==>         O(1)         /          O(N)

삽입 최대 시간 복잡도 ==>         O(N)        /           O(1)

 

ArrayList는 검색에는 상수시간이 걸리지만, 삽입에는 모든 원소의 칸을 옮겨야할 수 있기 때문에 O(N)이 걸린다.

반면 LinkedList는 참조를 따라서 가기때문에 최악의 경우 검색에 O(N)이 걸리지만, 삽입시에는 참조 연결만 해주면 되기 때문에 상수 시간이 걸린다.

 

위 문제는 List 중간에 노드를 삽입하는 경우는 없고, 검색하거나 맨 마지막에 노드를 추가하는 경우만 있다.

따라서 ArrayList를 쓰면 검색, 추가 모두 상수 시간에 해결이 가능한 것이다.

하지만 LinkedList를 쓰면, N의 범위가 2<=N<=300,000이므로 최악의 경우 한 번의 검색에 300,000번의 연산이 필요하게 되는 것이다.

 

따라서 LinkedList 대신 ArrayList를 쓰면 시간 초과가 해결되어 통과가 된다.

 

근데 위 문제는 모든 거리의 길이가 1이므로 BFS를 사용하는 것이 더 바람직해 보인다.

 

데익스트라에 관한 풀이는 아래 링크를 타면된다.

https://chaechaeros.tistory.com/112

[백준 1916번] 최소비용 구하기 - JAVA

 

제출코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

import static java.lang.String.valueOf;

public class Main {

    static ArrayList<ArrayList<Node>> graph=new ArrayList<>();
    static int N,M,K,X;
    static boolean visited[];
    static int dist[];
    static final int INF=987654321;

    static class Node implements Comparable<Node>{
        int number;
        int weight;

        public int getNumber() {
            return number;
        }

        public int getWeight() {
            return weight;
        }

        public Node(int number, int weight){
            this.number=number;
            this.weight=weight;
        }

        @Override
        public int compareTo(Node node){
            return this.weight>node.weight?1:-1;
        }
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start,1));
        dist[start]=0;

        while(!pq.isEmpty()){
            Node tempNode=pq.poll();
            int now=tempNode.getNumber();

            if(visited[now]) continue;

            visited[now]=true;
            for(Node i:graph.get(now)){
                if(!visited[i.getNumber()] && dist[i.getNumber()]>dist[now]+1){
                    dist[i.getNumber()]=dist[now]+1;
                    pq.offer(new Node(i.getNumber(),dist[i.getNumber()]));
                }
            }
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());
        K=Integer.parseInt(st.nextToken());
        X=Integer.parseInt(st.nextToken());

        visited=new boolean[N+1];
        dist=new int[N+1];

        for(int i=0;i<N+1;++i){
            graph.add(new ArrayList<>());
        }
        Arrays.fill(dist,INF);

        for(int i=0;i<M;++i){
            st=new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken());
            int end=Integer.parseInt(st.nextToken());
            graph.get(start).add(new Node(end,1));
        }

        dijkstra(X);

        for(int i=0;i<dist.length;++i){
            if(dist[i]==K){
                sb.append(i).append('\n');
            }
        }

        if (sb.length() == 0) {
            System.out.println(-1);
        }
        else {
            System.out.println(sb);
        }
    }
}