[백준] 1753번 - 최단경로 (Java)

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

1753번: 최단경로

 

<문제 분석>

1. 다익스트라 알고리즘을 사용

2. 정점은 인접행렬로 구성하고, 방향이 있는 그래프이니 s -> e만 배열에 저장할 것.

 

<코드 구현 - 인접행렬>

import java.util.*;

/*
[백준] 1753번 - 최단경로 (Java)
*/

public class Main {
    static int V, E, K;
    static int[][] map;
    static int[] visited;

    void InputData() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();
        map = new int[V+1][V+1];
        for (int i=0; i<E; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int cost = in.nextInt();
            map[s][e] = cost;
            //map[e][s] = cost;
        }
    }
    void BFS(int start) {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(start);
        visited[start] = 0;
        while (!Q.isEmpty()) {
            int node = Q.poll();
            for (int i=1; i<=V; i++) {
                if (map[node][i] == 0) continue;
                Q.offer(i);
                visited[i] = Math.min(visited[i], visited[node] + map[node][i]);
                
            }
        }
    }

    static final int INF = Integer.MAX_VALUE;
    void Solve() {
        visited = new int[V+1];
        Arrays.fill(visited, INF);
        BFS(K);
        for (int x : visited) {
            if (x == 0) continue;
            if (x == INF)
                System.out.println("INF");
            else
                System.out.println(x);
        }

    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<결과 분석 #1>

메모리 제한이 256MB인데 배열 크기가 int map[20000][20000] 사용하기 때문에 1,600,000,000바이트로 초과가 된다.

인접리스트 방식으로 재구현해야 한다. ArrayList에 정점과 가중치를 동시에 저장하기 위해서는 구조체를 만들어야 한다.

 

 

<코드구현 - 인접리스트>

import java.util.*;

/*
[백준] 1753번 - 최단경로 (Java)
*/

public class Main {
    static int V, E, K;
    ArrayList<Node> list[];
    static int[] visited;

    class Node {
        int v;
        int c;
        Node (int v, int c) {
            this.v = v;
            this.c = c;
        }
    }
    void InputData() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();
        list = new ArrayList[V+1];
        for (int i=1; i<=V; i++) {
            list[i] = new ArrayList<Node>();
        }
        
        for (int i=0; i<E; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int cost = in.nextInt();
            list[s].add(new Node(e, cost));
        }
    }
    void BFS(int start) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(new Node(start, 0));
        visited[start] = 0;
        while (!Q.isEmpty()) {
            Node node = Q.poll();
            for (Node x : list[node.v]) {
                Q.offer(new Node(x.v, x.c));
                visited[x.v] = Math.min(visited[x.v], visited[node.v] + x.c);
            }
        }
    }

    static final int INF = Integer.MAX_VALUE;
    void Solve() {
        visited = new int[V+1];
        Arrays.fill(visited, INF);
        BFS(K);
        for (int i=1; i<=V; i++) {
            if (visited[i] == INF)
                System.out.println("INF");
            else
                System.out.println(visited[i]);
        }

    }

	public static void main(String[] args) {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<결과 분석 #2>

1. PriorityQueue 사용해야함.(시간 초과)

2. 방문배열을 추가로 사용해서 큐에서 꺼낸 노드가 방문한 곳이면 스킵해야함.(시간 초과)

3. 최단거리가 업데이트가 될 때만 큐에 넣도록 수정.(메모리 초과)

4. 큐에 넣을 때 지금까지 누적거리를 넣어야 함.(시간 초과)

5. StringBuilder를 사용해서 결과 출력.(시간 초과) -> 큰 영향 없음

6. 방문배열 사용해서 방문한 정점이면 스킵. (시간 초과) -> 3번만 해도 충분함.

 

<코드>

import java.util.*;
import java.io.*;

/*
[백준] 1753번 - 최단경로 (Java)
*/

public class Main {
    static int V, E, K;
    ArrayList<Node> list[];
    static int distance[];
    static boolean visited[];   

    // PQ로 성능개선을 안하면 시간초과 발생함.
    class Node implements Comparable<Node> {
        int v;
        int c;
        Node (int v, int c) {
            this.v = v;
            this.c = c;
        }

        @Override
        public int compareTo(Node o) {
            return this.c - o.c;
        }
    }
    void InputData() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();
        list = new ArrayList[V+1];
        for (int i=1; i<=V; i++) {
            list[i] = new ArrayList<Node>();
        }
        
        for (int i=0; i<E; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int cost = in.nextInt();
            list[s].add(new Node(e, cost));
        }
    }

    void BFS(int start) {
        PriorityQueue<Node> PQ = new PriorityQueue<>();
        PQ.offer(new Node(start, 0));
        distance[start] = 0;

        while (!PQ.isEmpty()) {
            Node node = PQ.poll();
            int now_v = node.v;
            int now_c = node.c;
            // 이미 방문한 노드면 스킵(시간 초과)
            if (visited[now_v]) continue;
            visited[now_v] = true;

            for (Node x : list[now_v]) {
                // 최단거리가 업데이트 될 때만 큐에 넣도록 수정(메모리 초과)
                int next_v = x.v;
                int next_c = x.c;
                if ((distance[now_v] + next_c) < distance[next_v]) {
                    distance[next_v] = distance[now_v] + next_c;
                    //PQ.offer(new Node(next_v, next_c));
                    // 현재까지 누적거리를 큐에 삽입함.(틀림)
                    PQ.offer(new Node(next_v, distance[next_v]));
                }
            }
        }
    }

    static final int INF = Integer.MAX_VALUE;
    void Solve() throws Exception {
        distance = new int[V+1];
        visited = new boolean[V+1];
        Arrays.fill(distance, INF);
        BFS(K);
        // for (int i=1; i<=V; i++) {
        //     if (distance[i] == INF)
        //         System.out.println("INF");
        //     else
        //         System.out.println(distance[i]);
        // }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        for (int i=1; i<=V; i++) {
            if (distance[i] == INF)
                sb.append("INF\n");
            else
                sb.append(distance[i]+"\n");
        }
        bw.write(sb.toString());
        bw.close();
        
        

    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<최종 제출 코드>

import java.util.*;
import java.io.*;

/*
[백준] 1753번 - 최단경로 (Java)
*/

public class Main {
    static int V, E, K;
    ArrayList<Node> list[];
    static int distance[];

    // PQ로 성능개선을 안하면 시간초과 발생함.
    class Node implements Comparable<Node> {
        int v;
        int c;
        Node (int v, int c) {
            this.v = v;
            this.c = c;
        }
        @Override
        public int compareTo(Node o) {
            return this.c - o.c;
        }
    }
    void InputData() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();
        list = new ArrayList[V+1];
        for (int i=1; i<=V; i++) {
            list[i] = new ArrayList<Node>();
        }
        
        for (int i=0; i<E; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int cost = in.nextInt();
            list[s].add(new Node(e, cost));
        }
    }

    void dijkstra(int start) {
        PriorityQueue<Node> PQ = new PriorityQueue<>();
        PQ.offer(new Node(start, 0));
        distance[start] = 0;

        while (!PQ.isEmpty()) {
            Node now = PQ.poll();
            for (Node next : list[now.v]) {
                // 최단거리가 업데이트 될 때만 큐에 넣도록 수정(메모리 초과)
                if ((distance[now.v] + next.c) < distance[next.v]) {
                    distance[next.v] = distance[now.v] + next.c;
                    // 현재까지 누적거리를 큐에 삽입함.
                    PQ.offer(new Node(next.v, distance[next.v]));
                }
            }
        }
    }

    static final int INF = Integer.MAX_VALUE;
    void Solve() throws Exception {
        distance = new int[V+1];
        //visited = new boolean[V+1];
        Arrays.fill(distance, INF);
        dijkstra(K);
        for (int i=1; i<=V; i++) {
            if (distance[i] == INF)
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}