[백준]1916_최소비용구하기_다익스트라_Java 풀이 + 반례와 효율 비교

이지은·2023년 2월 8일
0

1916번: 최소비용 구하기

풀이

처음에 인접행렬로 풀었더니 애먹은 경우가 있었다. 그래서 총 3가지 풀이를 준비했다.

  1. 인접행렬 int [][] map = new int[N+1][N+1];

  2. 인접리스트 ArrayList [] map = new ArrayList[N+1];

  3. 인접리스트 ArrayList<ArrayList map = new ArrayList<>();

참고할 반례

  • 반례(출발지와 도착지가 같은데 비용이 다른 경우가 있을 수 있음) 2
    2
    1 2 10
    1 2 20
    1 2
    → 10
  • 반례2(버스비용은 0보다 크거나 같고) 2
    1
    1 2 0
    1 2 → 0

코드

package Graph;
// 다익스트라 ( 음이 아닌 가중 그래프에서 단일 쌍, 단일 출발, 단일 도착) (최단 경로(최소비용))
// 인접 행렬
import java.io.*;
import java.util.*;

public class Main_1916 {
    static class Vertex implements Comparable<Vertex> {
        int no, minDist; // 정점 번호, 출발지에서 자신으로 최소비용

        public Vertex(int no, int minDist){
            super();
            this.no = no;
            this.minDist = minDist;
        }

        @Override
        public int compareTo(Vertex o){
            return this.minDist - o.minDist;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int [][] adjMatrix = new int[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(i==j){
                    adjMatrix[i][j] = 0;
                    continue;
                }
                adjMatrix[i][j]=Integer.MAX_VALUE;
            }
        }
        StringTokenizer st = null;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int depart = Integer.parseInt(st.nextToken());
            int arrive = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adjMatrix[depart][arrive] = Integer.min(adjMatrix[depart][arrive],cost);

        }
        st = new StringTokenizer(br.readLine());
        int depart = Integer.parseInt(st.nextToken());
        int arrive = Integer.parseInt(st.nextToken());

        int [] dist = new int[N+1];
        boolean[] visit = new boolean[N + 1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[depart] = 0;

        PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
        pq.offer(new Vertex(depart, dist[depart]));

        while(!pq.isEmpty()){
            Vertex now = pq.poll();

            if(visit[now.no]) continue;

            visit[now.no] = true;

            for (int i = 1; i <= N; i++) {
                if(adjMatrix[now.no][i] != Integer.MAX_VALUE && !visit[i] &&
                dist[i] > dist[now.no] + adjMatrix[now.no][i]){
                    dist[i] = dist[now.no] + adjMatrix[now.no][i];
                    pq.offer(new Vertex(i,dist[i]));
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(dist[arrive]);
        System.out.println(sb);

    }
}
package Graph;
// 다익스트라 인접리스트 ArrayList<Vertex>[] map = new ArrayList[N + 1];
import java.io.*;
import java.util.*;
import java.lang.*;

public class Main_1916_2 {
    static class Vertex implements Comparable<Vertex> {
        int no,minDist;

        public Vertex(int no, int minDist){
            super();
            this.no = no;
            this.minDist = minDist;
        }

        @Override
        public int compareTo(Vertex o){
            return this.minDist - o.minDist;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<Vertex>[] map = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int depart = Integer.parseInt(st.nextToken());
            int arrive = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[depart].add(new Vertex(arrive, cost));
        }
        st = new StringTokenizer(br.readLine());
        int depart = Integer.parseInt(st.nextToken());
        int arrive = Integer.parseInt(st.nextToken());

        int dist[] = new int[N + 1];
        boolean visit[] = new boolean[N + 1];
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[depart] = 0;
        pq.add(new Vertex(depart,dist[depart]));

        while (!pq.isEmpty()) {
            Vertex now = pq.poll();

            if (visit[now.no]) continue;

            visit[now.no] = true;

            for (Vertex newVertex:map[now.no]) {
                if(dist[newVertex.no] > dist[now.no] + newVertex.minDist){
                    dist[newVertex.no] = dist[now.no] + newVertex.minDist;
                    pq.add(new Vertex(newVertex.no, dist[newVertex.no]));
                }
            }
        }

        sb.append(dist[arrive]);
        System.out.println(sb);
    }
}
package Graph;
// 다익스트라 인접 리스트 ArrayList<ArrayList<Vertex>> map2 = new ArrayList<>();
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_1916_3 {
    static class Vertex implements Comparable<Vertex> {
        int no,minDist;

        public Vertex(int no, int minDist){
            super();
            this.no = no;
            this.minDist = minDist;
        }

        @Override
        public int compareTo(Vertex o){
            return this.minDist - o.minDist;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

//        ArrayList<Vertex>[] map = new ArrayList[N + 1];
        ArrayList<ArrayList<Vertex>> map2 = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
//            map[i] = new ArrayList<>();
            map2.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int depart = Integer.parseInt(st.nextToken());
            int arrive = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

//            map[depart].add(new Vertex(arrive, cost));
            map2.get(depart).add(new Vertex(arrive, cost));
        }
        st = new StringTokenizer(br.readLine());
        int depart = Integer.parseInt(st.nextToken());
        int arrive = Integer.parseInt(st.nextToken());

        int dist[] = new int[N + 1];
        boolean visit[] = new boolean[N + 1];
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[depart] = 0;
        pq.add(new Vertex(depart,dist[depart]));

        while (!pq.isEmpty()) {
            Vertex now = pq.poll();

            if (visit[now.no]) continue;

            visit[now.no] = true;

//            for (Vertex newVertex:map[now.no]) {
            for(Vertex newVertex:map2.get(now.no)){
                if(dist[newVertex.no] > dist[now.no] + newVertex.minDist){
                    dist[newVertex.no] = dist[now.no] + newVertex.minDist;
                    pq.add(new Vertex(newVertex.no, dist[newVertex.no]));
                }
            }
        }

        sb.append(dist[arrive]);
        System.out.println(sb);
    }
}

효율 비교

  1. 인접행렬 int [][] map = new int[N+1][N+1];

    평균최대최소
    메모리478964834047532
    시간479.2544392



  2. 인접리스트 ArrayList<Vertex>[] map = new ArrayList[N + 1];

    평균최대최소
    메모리519125228851324
    시간492.8524468


  3. 인접리스트 ArrayList<ArrayList<Vertex>> map2 = new ArrayList<>();

    평균최대최소
    메모리51921.65232051472
    시간502.4520488



평균 메모리 : 1<2<3

최대 메모리 : 1<2<3

최소 메모리 : 1<2<3

평균 시간 : 1<2<3

최대 시간 : 1<3<2

최소 시간 : 1<2<3

정점(최대 1,000)보다 간선(최대 100,000)이 많아서 그런지 인접행렬이 인접리스트보다 뛰어난 효율을 보여주었다.

-> 간선이 많은 그래프는 인접행렬로, 간선이 적은 그래프는 인접리스트로 구현하면 좋을 것 같다.

profile
이지은
즐겁
이전 포스트

[Java] 자바 배열 복사하기

다음 포스트

[MySQL] JOIN 총 정리

0개의 댓글