백준 1753번 자바 ☆

1. 문제

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

1753번: 최단경로

 

2. 접근 방식

다익스트라 알고리즘을 활용한다.

 

최소, 최단 등 관련 문제는 BFS, 다익스트라, 플로이드 와샬등의 알고리즘으로 해결하는 것이 일반적이다.

 

가중치 개념이 없는 경우, 2차원 배열의 맵에서 최소,최단 거리를 구할때는 BFS를

가중치 개념이 있는 경우, 한 가지의 노드를 기준으로 다른 노드들의 최소,최단거리는 Dijkstra를

                                         모든 노드 간의 최소, 최단 거리는 Floyd Warshall을 사용한다.

 

해당 문제의 경우 가중치 개념이 있으면서 시작 노드를 지정해주기 때문에 정석적인 Dijkstra 알고리즘을 사용할 수 있다.

 

다익스트라?

• 에지(가중치)가 모두 양수
• 시간복잡도 - O(ElogV)

인접리스트, 최단거리 배열(각 노드간 최단거리를 담는 배열)이 필요

우선순위 큐를 안쓰면 모든 에지를 탐색하므로 메모리초과가 발생 

3. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int V,E,start;
	static int[] shortest;
	static List<Node>[] nodes;
	static boolean[] visited;
	
	static class Node implements Comparable<Node> {
		int node;
		int edge;
		public Node (int node, int edge) {
			this.node = node;
			this.edge = edge;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.edge - o.edge;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		shortest = new int[V+1];
		nodes = new ArrayList[V+1];
		
		Arrays.fill(shortest, 10000000);
		shortest[start] = 0;
		for (int i=1; i<=V; i++) {
			nodes[i] = new ArrayList<Node>();
		}
		for (int i=1; i<=E; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			nodes[u].add(new Node(v, w));
		}
		
		dijkstra();
		for (int i=1; i<=V; i++) {
			if (i == start) {
				System.out.println(0);
				continue;
			}
			if (!visited[i]) {
				System.out.println("INF");
				continue;
			}
			System.out.println(shortest[i]);
		}
	}
	
	public static void dijkstra() {
		visited = new boolean[V+1];
		PriorityQueue<Node> q = new PriorityQueue<Node>();
		q.add(new Node(start, 0));
		
		while (!q.isEmpty()) {
			Node now = q.poll();
			if (visited[now.node]) {
				continue;
			}
			visited[now.node] = true;
			for (Node next : nodes[now.node]) {
				shortest[next.node] = Math.min(shortest[next.node], shortest[now.node] + next.edge);
				q.add(new Node(next.node, shortest[next.node]));		
			}
		}
	}
}

 

4. 정리

계속 메모리 초과가 나서 애를 먹었다. 방문배열을 안쓰려면 우선순위 큐에 노드를 삽입할 때 거리가 작은 경우를 Math.min이 아닌 if문으로 비교 후 if문안에서 노드를 삽입해줘야 메모리 초과가 안난다.