[백준 / JAVA] 1916. 최소비용 구하기(G5)

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

 

백준 플레 도전을 한 후 일주일 간 포스팅이 멈췄는데, 니가 그럼 그렇지라고 생각하겠지만 의외로 문제를 안 푼건 아니다. 못 풀었다.

BFS로 풀었더니 메모리가 초과되서 DFS로 다시 풀었더니 시간이 초과되는 문제를 3번 연속으로 만나서 던졌을 뿐이다...그래도 다익스트라 새로 정리했으니 조아쓰! 

 

 

문제 진짜 기본적인 다익스트라를 묻고 있다.

 

메모리 초과 = BFS, 시간 초과 = DFS

 

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		Graph graph = new Graph(n);
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			graph.addEdge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken()));
		}
		st = new StringTokenizer(br.readLine());
		System.out.println(graph.Dijkstra(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
	}

	static class Graph {
		Deque<Node>[] dqArr; // 연결 노드를 저장할 자료구조
		int nodeCount; // 노드 개수

		public Graph(int nodeCount) { // 그래프 선언
			this.nodeCount = nodeCount;
			dqArr = new Deque[nodeCount + 1];
			for (int i = 0; i < dqArr.length; i++)
				dqArr[i] = new ArrayDeque<>();
		}

		void addEdge(int start, int dest, int cost) { // 그래프에 간선 추가
			dqArr[start].add(new Node(dest, cost));
		}

		public int Dijkstra(int start, int dest) { // 다익스트라
			PriorityQueue<Node> pq = new PriorityQueue<Node>();
			boolean visited[] = new boolean[nodeCount + 1];
			int dist[] = new int[nodeCount + 1]; // 거리 저장 배열
			Arrays.fill(dist, Integer.MAX_VALUE); // 모두 최댓값으로 초기화
			dist[start] = 0; // 출발지 거리 = 0
			pq.add(new Node(start, 0));

			while (!pq.isEmpty()) {
				int cur = pq.poll().index;

				if (visited[cur]) // 이미 방문한 노드라면
					continue;
				visited[cur] = true;

				for (Node next : dqArr[cur]) { // 현재 노드와 인접한 노드 리스트
					if (dist[next.index] > dist[cur] + next.cost) { // 현재 next의 가중치가 cur을 경유하는 값보다 크다면
						dist[next.index] = dist[cur] + next.cost;

						pq.add(new Node(next.index, dist[next.index])); // 여기서 next가 다음의 cur이 됨
					}
				}
			}
			return dist[dest];
		}

		class Node implements Comparable<Node> {
			int index, cost;

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

			@Override
			public int compareTo(Graph.Node o) { // PriorityQueue 비교 조건
				return Integer.compare(this.cost, o.cost);
			}
		}
	}
}