[ 백준 ] 1753번 최단경로 문제풀이 feat. 자바 JAVA

[ 백준 ] 1753번 최단경로 문제풀이 feat. 자바 JAVA

 

문제

 

문제풀이방법

이 문제의 특징을 알아보자.

1. 방향이 있는 그래프이다.

2. 시작점이 주어지고 그 점에서 다른 점으로 가는 최단 경로를 구하는 문제이다.

3. 가중치가 존재한다. ( w는 10 이하의 자연수 )

 

-> 가중치가 양수이고, 특정점이 주어지고 다른 점으로 가는 모든 최단 경로를 구하는 조건들을 봤을 때, 

이 문제는 전형적인 다익스트라 문제이다. 

 

 

생각해볼만한 것

1. Queue를 써서 풀어도 되는 것 아닌가?

    - Queue를 사용한다는 것은 결국 BFS 구현이 된다.

    - 값이 작을 때는 문제의 해는 올바른 값을 도출한다.

    - 하지만, 시간초과가 날 것이다.

 

2. visited를 꼭 써야하나? ( 방문한 노드를 체크하는 것 ) 

     - 방문한 곳을 체크하지 않으면 메모리초과가 난다.

 

 

코드

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

public class ShortestPath_1753 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());

        int[] dist = new int[V+1];
        boolean[] visited = new boolean[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;

        ArrayList<Pair>[] graph = new ArrayList[V+1];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }

        int u,v,w;
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            graph[u].add(new Pair(v, w));
        }

		// 다익스트라
        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> a.w - b.w);
        pq.add(new Pair(K, 0));

        while (!pq.isEmpty()) {
            Pair p = pq.poll();

            if(visited[p.i]) continue;

            for(int i=0; i<graph[p.i].size(); i++) {
                int next = graph[p.i].get(i).i;
                int weight = graph[p.i].get(i).w;

                dist[next] = Math.min(dist[next], dist[p.i] + weight);
                pq.add(new Pair(next, dist[next]));
            }

            visited[p.i] = true;
        }

		//출력코드
        for (int i = 1; i < dist.length; i++) {
            if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dist[i]);
        }
    }

    static class Pair{
        int i, w;

        Pair(int i, int w) {
            this.i = i;
            this.w = w;
        }
    }
}

 

 

문제링크

www.acmicpc.net/problem/1753

1753번: 최단경로