[백준] 1916 : 최소비용 구하기 - JAVA [자바]

안녕하세요.

오늘은 [백준] 1916 : 최소비용 구하기 문제를 풀어보도록 하겠습니다.

 

 

 

📌 접근

다익스트라 알고리즘을 적용해서 풀이하면 됩니다.

 

다익스트라 알고리즘은,

모든 가중치가 양수인 무방향 그래프에서 최소 비용을 구하는 문제에 적합합니다.

 

출발점에서 제일 가까운 노드를 먼저 탐색하며, 각 노드까지의 최소비용을 갱신합니다.

다익스트라는 항상 "가장 가까운 노드부터" 꺼내기 때문에, 한 번 꺼낸 노드는 그 시점에서의 거리가 최단 거리입니다.

 

다익스트라 알고리즘을 구현하기 위해서는 크게 4가지의 요소가 필요합니다.

1. pq 사용이 가능한 Comparable을 구현한 노드

2. 시작정점으로부터의 거리를 저장하는 dist 배열 (초기에 Integer.MAX_VALUE로 초기화 필수)

3. 각 노드별 연결노드 정보를 저장하는 adjList

4. 재탐색을 방지하는 visited 배열

// 1. Comparable을 구현한 노드
public static class Node implements Comparable<Node> {
	int v; // 연결된 정점
    int w; //간선의 가중치
    
    @Override
    public int compareTo(Node o) {
    	return w - o.w;
    }
}

// 2. 거리를 저장하는 dist 배열
public static int[] dist;

// 3. 연결정보를 저장하는 adjList
public static ArrayList<ArrayList<Node>> adjList;

// 4. 재탐색을 방지하는 visited 배열
public static boolean[] visited;

 

 

💻 풀이

// hyeblee
import java.util.*;
import java.io.*;

public class Main {

  public static int N, M;
  public static int[] dist;
  public static boolean[] visited;
  public static ArrayList<ArrayList<Node>> adjList;

  public static class Node implements Comparable<Node> {

    int v; // 연결된 노드의 번호
    int w; // 간선의 가중치(비용)

    public Node(int v, int w) {
      this.v = v;
      this.w = w;
    }

    @Override
    public int compareTo(Node o) {
      return w - o.w;
    }
  }


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

    while (!pq.isEmpty()) {
      Node cur = pq.poll();
      if (visited[cur.v]) {
        continue;
      }
      visited[cur.v] = true;

      for (Node neighbor : adjList.get(cur.v)) {
        if (dist[neighbor.v] > dist[cur.v] + neighbor.w) {
          dist[neighbor.v] = dist[cur.v] + neighbor.w;
          // 우선 큐에 새로운 dist 값으로 갱신하여 넣어준다.
          pq.offer(new Node(neighbor.v, dist[neighbor.v]));
        }
      }
    }
  }

  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()); // 버스 수

    dist = new int[N + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    visited = new boolean[N + 1];
    adjList = new ArrayList<>();

    for (int i = 0; i <= N; i++) {
      adjList.add(new ArrayList<>());
    }

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      int weight = Integer.parseInt(st.nextToken());
      adjList.get(start).add(new Node(end, weight));
    }
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());

    dist[start] = 0;
    dijkstra(start);

    System.out.println(dist[end]);
  }
}

 

🤔 고민했던 점 & 어려웠던 부분

처음에는 최소비용이므로 BFS를 써야한다고 생각했습니다.

하지만 BFS는 가중치가 있는 그래프의 탐색에는 사용할 수 없습니다. (가중치가 전부 같은 경우에만 적용 가능)

또한 방문을 처리하는 시점과 큐에 넣는 조건이 잘 이해가 가지 않았습니다..

 

정리❕❕❕

• 다익스트라 알고리즘은 모든 간선의 가중치가 양수이고, 다른 가중치를 갖고 있는 그래프의 최소 비용 탐색에 적합하다.
• 구현을 위해 Node, dist, visited, adjList가 필요하다.
• dist배열은 모든 값을 무한대로 초기화 시키고 시작해야한다. (단, 시작 정점의 값은 0)
• 인접리스트를 돌면서, 값을 갱신할 수 있다면 갱신 후 큐에 넣어준다. 
  (갱신조건: dist[neighbor.v] > dist[cur.v] + neighbor.w )
• 항상 가까운 노드부터 꺼내기 때문에, 한 번 꺼낸 노드는 꺼낸 시점에서의 거리가 최단경로이다.