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

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

접근 방법

다익스트라를 사용한다.

인접리스트를 사용하여, 겉의 리스트는 출발 도시, 안의 리스트는 연결되는 도시를 넣어준다.

리스트 안의 리스트를 사용할때에는 안의 리스트를 출발도시 수만큼 새로 생성해줘야 한다.

다익스트라 메서드에서 거리 테이블을 만들어준다. 초기는 무한값으로 설정해준다.

다익스트라에서는 메모리와 시간 절약을 위해 우선순위 큐를 사용했다. 가중치가 낮은 순서로 가져오기 때문에 낮은 가중치의 도시 선형탐색과 방문처리를 할 필요가 없어진다.

거리테이블에 있는 값과, 연결된 도시를 거쳐갈때를 비교해서 더 작은 값으로 갱신해준다. 갱신 후 연결노드로 처리하기 위해 큐에 넣어준다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_1916_최소비용구하기 {

	static int N, M;
	static final int INF = Integer.MAX_VALUE;
	static ArrayList<ArrayList<Node>> list;

	static class Node implements Comparable<Node> {
		int idx, cost; // 연결도시, 가중치

		public Node(int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) { // 가중치 오름차순 정렬
			return this.cost - o.cost;
		}

	}

	private static int dijkstra(int start, int end) {
		int[] dist = new int[N + 1]; // 0번째 버림

		// INF 초기화
		for (int i = 0; i < N + 1; i++) {
			dist[i] = INF;
		}

		// 최단거리 테이블 초기 설정 - 최소 거리 순으로 정렬 위해
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0)); // 초기 거리 넣어줌

		// 시작 거리 0
		dist[start] = 0;

		// dijkstra
		while (!pq.isEmpty()) {
			Node cur = pq.poll();

			// 현재 가중치가 더 크다면 진행 안함
			if (dist[cur.idx] < cur.cost)
				continue;

			// 현재 노드와 연결된 노드 파악
			for (int i = 0; i < list.get(cur.idx).size(); i++) {
				Node next = list.get(cur.idx).get(i); // 연결된 노드를 가져옴

				if (dist[next.idx] > cur.cost + next.cost) { // 거쳐가는 것이 더 비용이 작다면
					dist[next.idx] = cur.cost + next.cost;
					pq.offer(new Node(next.idx, dist[next.idx])); // 갱신된 거리를 큐에 넣어준다.
				}
			}
		}

		return dist[end];
	}

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

		N = Integer.parseInt(br.readLine()); // 도시의 개수
		M = Integer.parseInt(br.readLine()); // 버스의 개수

		list = new ArrayList<ArrayList<Node>>();

		for (int i = 0; i < N + 1; i++) { // 0번째 노드 버림
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			tokens = new StringTokenizer(br.readLine());

			// 출발 도시, 도착 도시, 버스 비용
			int start = Integer.parseInt(tokens.nextToken());
			int end = Integer.parseInt(tokens.nextToken());
			int cost = Integer.parseInt(tokens.nextToken());

			list.get(start).add(new Node(end, cost)); // 연결 도시 저장
		}

		tokens = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(tokens.nextToken()); // 출발 도시
		int E = Integer.parseInt(tokens.nextToken()); // 도착 도시

		System.out.println(dijkstra(S, E));

	}

}

처음에 행렬로 풀었었는데 틀린 답이 나왔다. 백준의 질문 게시판을 살펴보니 인접행렬을 사용했을 경우 중복값에 대한 처리가 어쩌구 써있어서 인접리스트를 사용했다.