[백준/Java] 1916번 : 최소비용 구하기

🌵 문제 분석

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

출발 도시 번호, 도착 도시 번호가 A, B로 주어질 때 A에서 B까지 가는 데 드는 최소 비용을 출력하여라.

입력 :

N(도시의 개수)

M(버스의 개수)

a(출발 도시 번호) b(도착 도시 번호) w(버스 비용)

...

A(구하려는 출발 도시 번호) B(구하려는 도착 도시 번호)

🌵 구현 아이디어

도시 개수가 최대 1,000개 이므로 인접 행렬로 구현하면 공간 복잡도가 1,000,000*4byte=4MB < 128MB이므로 인접 행렬로 구현해보겠다.

1️⃣ 인접 행렬을 간선 비용으로 채우기

예제 입력 1 :

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

인접 행렬을 arr[출발 도시 번호][도착 도시 번호] = 간선 비용 으로 채운다.

출발, 도착 도시가 정해져있으므로 단방향만 고려한다.

 

1 2 2 -> 도시1, 도시2 간선의 비용이 2이므로 arr[1][2] = 2 

1 3 3 -> 도시1, 도시3 간선의 비용이 3이므로 arr[1][3] = 3

...

완성하면 아래와 같다.

	1	2	3	4	5
1		2	3	1	10
2				2
3				1	1
4					3
5

 

2️⃣ DFS로 모든 A->B 경로의 간선 비용 구하기 

 

1->5로 가는 경로의 비용의 최소값을 구해야 한다.

모든 경로와 그 경로로 지나갔을 때 드는 비용을 구해보면 다음과 같다.

 

1->5 : 10

1->2->4->5 : 7

1->4->5 : 4

1->3->4->5 : 7

1->3->5 : 4

 

그 중 최소 비용은 4가 된다.

이처럼 A->B로 가는 모든 경로를 DFS 탐색하면서 비용의 최소값을 갱신한다.

 

1️⃣ 인접 리스트로 간선 정보 입력하기

인접 행렬을 사용하면 같은 노드 사이 간선이 두 개 존재할 때 간선 가중치가 덮어씌워질 수 있다.

예) 

1 2 5

1 2 3

 

따라서 인접 리스트 List<List<Node>>를 사용한다.

 

2️⃣ BFS+우선순위큐로 A->B 경로의 최소 간선 비용 구하기

1에서부터 출발해 각 노드에 도착할 때 최소 비용을 저장할 배열은 다음과 같다. 

초기값을 무한대로 설정해둔 이유는 더 작은 비용이 구해질 때마다 업데이트하기 위해서이다.

1	2	3	4	5
0	무한대	무한대	무한대	무한대

출발지인 1부터 시작. 1에서 갈 수 있는 노드는 2, 3, 4, 5이므로 비용을 업데이트해준다. (빨간색으로 표시)

그리고 1에서 갈 수 있는 노드를 모두 방문했으므로 방문 체크해준다. (초록색으로 표시)

1	2	3	4	5
0	2	3	1	10

아직 방문하지 않은 노드 중 비용이 가장 작은 노드는 4이므로 다음 탐색 노드는 4이다.

노드 4에서 갈 수 있는 노드는 5 하나이다.

기존 비용 10 VS 1에서 4를 거쳐 5로 갈 때의 비용은 1+3=4 둘을 비교하면 4가 더 작으므로 10을 4으로 업데이트한다.

그리고 4도 방문 체크해준다.

1	2	3	4	5
0	2	3	1	4

 

...

 

이런 식으로 나머지 노드들도 방문을 마치고 나면

인덱스 5에 있는 값이 1->5로 가는 데 드는 비용의 최소값이 된다.

 

🌵 시간 복잡도

• 인접 행렬을 채우는 시간 복잡도 : O(M)
• 다익스트라 탐색하는 시간 복잡도 : O(MlogN)
  
  • 모든 노드 탐색 O(N)
  • 모든 간선 확인 O(M)
  • 우선순위 큐 연산 O(MlogN)
    • 우선순위 큐에서 최소 거리 노드를 꺼내기(poll) -> heap구조에서 O(logN)
    • 갱신된 거리로 노드를 다시 넣기 (offer) -> O(logN) 
    • 최대 M개의 노드가 우선순위 큐에 삽입되고 각각 logN의 시간이 걸리므로 O(MlogN)
  • O(N + M + M log N) → O((N + M) log N) 그런데 보통 노드보다 간선이 많으므로 O(MlogN)이라고 봄

💡 다익스트라 탐색 과정 

1. 시작 노드를 우선순위 큐에 넣음
2. 큐에서 현재 최단 거리의 노드를 꺼냄
3. 꺼낸 노드에서 이동 가능한 모든 인접 노드를 확인하면서 최단 거리 갱신
4. 갱신된 거리로 다시 큐에 넣음

 

M<=100,000

N<=1,000

 

전체 시간 복잡도는 O(M)+O(MlogN) = 100,000+100,000*3이므로 제한 시간 (0.5초) 안에 탐색 가능하다.

🌵 알고리즘

그래프 탐색

❌ 오답 노트

📍 BFS는 간선의 가중치가 모두 같을 때 최소 비용을 구하는 경우에 쓰임

BFS는 모든 간선의 가중치가 동일할 때 최소 비용을 구하는 경우 적합하다. 

가중치가 동일하면 BFS로 도착지를 가장 빨리 찾았을 때가 비용이 최소가 되기 때문이다.

📍 DFS는 간선에 가중치가 있고 최소 비용을 구할 때 쓰면 비효율적임

DFS는 모든 경로를 다 확인하면서 최소 비용을 찾으므로 최단 거리나 최소 비용을 찾을 때 쓰기엔 비효율적이다. 

목적지 노드가 지금 찾는 경로에 없음에도 계속 깊이 탐색을 하면 불필요한 경로를 탐색하게 되기 때문이다.

 

내가 이 문제를 처음에 DFS로 구현해서 시간 초과가 발생한 것처럼. 아래는 시간 초과가 발생한 코드이다.

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

public class Main {
    static int N, M, A, B, minWeight;
    static int[][] arr;
    static boolean[][] check;

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        arr = new int[N+1][N+1];
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[c1][c2] = w;
        }

        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        minWeight = Integer.MAX_VALUE;
        check = new boolean[N+1][N+1];

        dfs(A, 0);
        System.out.println(minWeight);


    }
    static void dfs(int now, int weight){
        if(now==B){
            minWeight = Math.min(minWeight, weight);
            return;
        }
        for(int i=1; i<=N; i++){
            if(!check[now][i] && arr[now][i]!=0){
                check[now][i] = true;
                dfs(i, weight+arr[now][i]);
                check[now][i] = false;
            }
        }
    }
}

📍 다익스트라: 가중치를 고려한 BFS

다익스트라는 BFS처럼 노드를 너비 우선으로 탐색하지만 우선 순위 큐를 사용해서 '최소 비용 경로'를 먼저 탐색한다.

시간 복잡도는 O((N+M)logN)으로 DFS보다 더 효율적이다.

 

https://10000cow.tistory.com/entry/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%9C-%EC%82%B4%EB%8F%84-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[다익스트라 알고리즘] 한 살도 이해하는 다익스트라 알고리즘

 

이 블로그를 참고하면 이해하기 쉬움

 

💡가중치가 있는 그래프의 최단 거리를 구할 때는 다익스트라를 사용

일반적인 BFS는 가중치를 고려하지 않는다. 간선 가중치를 고려하지 않으므로 큐에 들어간 모든 노드들의 방문 우선순위는 같다. 그래서 그냥 가까운 순서대로 탐색할 뿐이다.

반면 다익스트라는 가중치를 고려한다. 우선순위 큐를 써서 가중치가 가장 작은 노드부터 방문할 수 있고, 이미 최단거리가 확정된 노드는 다시 방문하지 않게 할 수 있다. 그래서 탐색 경로가 효율적이다. BFS처럼 불필요한 경로를 탐색하지 않아도 된다.

 

다익스트라를 이 문제에 적용하면 num(도시 번호), weight(가중치) 변수를 가진 Node 클래스를 만들어서 

compareTo로 weight가 작은 순서대로 우선 순위 큐에 정렬시키고 weight 작은 곳부터 방문하게 한다. 

그리고 탐색 중 임의의 노드 K에 도착했을 때 이전에 구했던 경로의 가중치 합보다 현재 경로의 가중치 합이 더 크다면 더이상 탐색하지 않도록 무시하게 한다.

🌵 코드 설계

1. 입력 받기
   1. N에 도시 개수, M에 버스 개수 저장
   2. arr[N+1][N+1]에 M개의 간선 정보와 비용 저장
   3. A에 출발 도시, B에 도착 도시 저장
2. 필요한 자료구조 선언
   1. 도시를 방문했는지 체크할 배열 check[] 선언 
   2. 도시마다 최소 비용을 저장할 배열 ans[] 선언
      ans[A] = 0, 나머지는 Integer.MAX_VALUE로 초기화
   3. 우선순위 큐에 넣을 노드 클래스 Node 선언, 변수로 num, weight를 두기
      Comparable로 weight 기준 오름차순 정렬 구현
3. DFS로 A->B로의 최소 비용 구하기
   
   1. 재귀함수 인자로 now(현재 도시 번호), weight(가중치) 받기
   2. now가 B이면 minWeight 업데이트 하기
      minWeight = Math.min(minWeight, weight);
   3. 현재 도시와 인접한 모든 도시를 방문하며 재귀 탐색, now 방문 체크
      for(0<=i<N)
          if(!check[now]) dfs(i, weight += arr[now][i]);
      check[now] = true;
4. 다익스트라로 A->B로의 최소 비용 구하기
   1. 우선순위 큐에 출발 노드 A 넣기
   2. 큐가 빌 때가지 아래 과정 반복
      1. 비용이 제일 낮은 노드를 우선순위 큐에서 꺼내기
         Node now = pq.poll();
      2. now와 인접한 모든 노드 방문하면서 최소 비용 갱신한 후 우선순위 큐에 넣기, now방문체크
             if(!check[now])
                 for(0<i<=N)
                     int newWeight =  arr[now.num][i]+now.weight;
                     if(newWeight<ans[now.num]) ans[now.num] = newWeight; pq.offer(new Node(i, newWeight);
             check[now.num] = true; 

🌵 정답 코드

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

public class Main {
    static int N, M, A, B, minWeight;
    static List<List<Node>> list;
    static int[] ans;

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        for(int i=0; i<=N; i++){
            list.add(new ArrayList<>());
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(c1).add(new Node(c2, w));
        }

        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        minWeight = Integer.MAX_VALUE;
        ans = new int[N+1];
        Arrays.fill(ans, Integer.MAX_VALUE);
        ans[A] = 0;

        dijkstra(A);
        System.out.println(ans[B]);
    }

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

        while(!pq.isEmpty()){
            Node now = pq.poll(); //큐에서 한 개 꺼내기
            if(now.weight > ans[now.num]) continue; //기존 최단 거리보다 크면 무시

            for(Node next: list.get(now.num)){ //now와 인접한 노드들
                int newWeight = next.weight + ans[now.num];
                if(newWeight < ans[next.num]){
                    ans[next.num] = newWeight;
                    pq.offer(new Node(next.num, newWeight));
                }

            }

        }
    }
}

class Node implements Comparable<Node>{
    int num, weight;
    Node(int num, int weight){
        this.num = num;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o){
        return this.weight - o.weight;
    }
}