본문 바로가기
공부/알고리즘

[백준]1916_최소비용 구하기_다익스트라 인접행렬, 인접리스트 Java풀이 + 반례

by happyeuni 2023. 2. 8.

1916번: 최소비용 구하기

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

 

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

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

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

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

 

참고할 반례

- 출발지와 도착지가 같은데 비용이 다른 경우가 있을 수 있음

2

2

1 2 10

1 2 20

1 2

→ 10

 

- 버스 비용은 0보다 크거나 같음

2

1

1 2 0

1 2

-> 0

 

 

1번 풀이

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);

    }
}

  평균 최대 최소
메모리 47896 48340 47532
시간 479.2 544 392

 

 

2번 풀이

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);
    }
}

  평균  최대  최소
메모리 51912 52288 51324
시간 410.6 524 468

 

 

3번 풀이

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);
    }
}

  평균  최대  최소
메모리 51,921.6 52320 51472
시간 502.4 520 488

 

평균 메모리 : 1<2<3

최대 메모리 : 1<2<3

최소 메모리 : 1<2<3

 

평균 시간 : 1<2<3

최대 시간 : 1<3<2

최소 시간 : 1<2<3

 

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

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

 

 

 

 

'공부 > 알고리즘' 카테고리의 다른 글

[프로그래머스]42840_모의고사_완전탐색 Java 풀이  (0) 2023.02.15
[백준]20413_MVP 다이아몬드 (Easy)_그리디 Java 풀이  (0) 2023.02.14
[백준]17413_단어 뒤집기 2_Java 풀이  (0) 2023.02.04
[프로그래머스]42576_완주하지 못한 선수_Java 풀이 2가지  (0) 2023.01.25
[백준]1018_체스판 다시 칠하기_Java 풀이  (1) 2023.01.24

관련글

댓글

티스토리툴바