[백준 - Java] 1753번 : 최단경로

문제

www.acmicpc.net/problem/1504www.acmicpc.net/problem/1753

1753번: 최단경로

설명

다익스트라 구현 시 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데, 

간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라 

시간 복잡도 역시 O(V^2)으로 좋지 못하게 된다.

 

최단 경로 (다익스트라 알고리즘) FAQ

 

따라서 인접리스트로 그래프를 입력받았다.

 

또한 우선순위 큐를 사용해 다익스트라 알고리즘을 구현함으로써 훨씬 더 시간 복잡도를 줄였다.

---

 

📌 다익스트라 알고리즘에 대해 더 알고 싶다면 아래 포스팅을 참고해주세요!

[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘

전체 코드 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		int E = sc.nextInt();

		int start = sc.nextInt(); // 시작 정점 

		// 인접 리스트 구현 
		ArrayList<Element>[] adjList = new ArrayList[V+1];
		for(int i = 1; i < V+1; i++) {
			adjList[i] = new ArrayList<>();
		}

		for(int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();

			adjList[u].add(new Element(v, w));
		}

		boolean[] check = new boolean[V+1];

		int[] distance = new int[V+1];
		int INF = 10 * (V-1) + 1; // INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 한다.
		Arrays.fill(distance, INF);
		distance[start] = 0;
		
		PriorityQueue<Element> pq = new PriorityQueue<>();
		pq.offer(new Element(start, 0));
		
		while(!pq.isEmpty()) {
			int current = pq.poll().index;
			
			if(check[current]) continue;
			check[current] = true;
			
			for(Element next : adjList[current]) {
				if(distance[next.index] > distance[current] + next.distance) {
					distance[next.index] = distance[current] + next.distance;
					pq.offer(new Element(next.index, distance[next.index]));
				}
			}
		}

		for(int i = 1; i < V+1; i++) {
			if(distance[i] ==  INF)
				System.out.println("INF");
			else
				System.out.println(distance[i]);
		}
	}

}

class Element implements Comparable<Element> {
	int index;
	int distance;

	Element(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	@Override
	public int compareTo(Element o) {
		//return this.distance <= o.distance ? -1 : 1;
		return Integer.compare(this.distance, o.distance);
		
		/*
		 Integer.compare(int x, int y)
		 x == y ->  0 return 
		 x < y  ->  -1 return 
		 x > y  ->  1 return 
		 */
	}
}

코드 2

우선순위 큐를 사용하지 않고 기존 반복문으로 구현한 다익스트라 알고리즘이다.

하지만 BufferedReader를 사용해 입력받아야 한다. Scanner 사용하면 시간 초과남.

 

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

public class Main {

	public static void main(String[] args) throws IOException {    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());   
		int E = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine()); 

		// 인접 리스트 구현 
		ArrayList<Element>[] adjList = new ArrayList[V+1];
		for(int i = 1; i < V+1; i++) {
			adjList[i] = new ArrayList<>();
		}

		for(int i = 0; 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());

			adjList[u].add(new Element(v, w));
		}

		boolean[] check = new boolean[V+1];

		int[] distance = new int[V+1];
		int INF = 10 * (V-1) + 1; // INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 한다.
		Arrays.fill(distance, INF);
		distance[start] = 0;

		for(int i = 0; i < V-1; i++) {
			int min = Integer.MAX_VALUE;
			int current = -1;

			for(int j = 1; j < V+1; j++) {
				if(!check[j] && distance[j] < min) {
					min = distance[j];
					current = j;
				}
			}

			check[current] = true;

			for(Element next : adjList[current]) {
				if(!check[next.index] && distance[current] + next.distance < distance[next.index]) {
					distance[next.index] = distance[current] + next.distance;
				}
			}
		}

		for(int i = 1; i < V+1; i++) {
			if(distance[i] ==  INF)
				System.out.println("INF");
			else
				System.out.println(distance[i]);
		}
	}

}

class Element implements Comparable<Element> {
	int index;
	int distance;

	Element(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}

	@Override
	public int compareTo(Element o) {
		return this.distance <= o.distance ? -1 : 1;
		//return Integer.compare(this.distance, o.distance);
	}
}

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%231753/src

KwonMinha/BOJ