[BOJ] 1753번 최단경로

링크

1753

풀이

참고 풀이
이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이할 수 있다.

다익스트라는 음의 가중치를 가지는 경우 사용할 수 없다.

다익스트라를 구현할 때 인접 행렬, 인접 리스트 둘 다 구현할 수 있는데 리스트가 효율적인 경우가 많기 때문에 인접 리스트로 구현하였다.

다익스트라는 한 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

이때 최단거리를 저장하는 배열 + 우선순위 큐를 이용하여 구현할 수 있다.

코드

우선순위큐를 쓰지 않고 시간복잡도 2V^2, 메모리 초과 발생한 코드

package Baekjoon;

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_1753_최단경로 {

	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());//간선 수
		st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());//시작 정점
		//서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다. -> 이차원배열은 안되겟네 -> 연결리스트?
		//pQ ? 가장 가중치가 작은 간선을 뽑을 리스트
		int[][] map = new int[V+1][V+1];
		for(int i =0 ; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
		}
		
		int[] dis = new int[V+1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[K] = 0;
		boolean[] vis = new boolean[V+1];
		for(int i =1 ; i <= V; i++) {
			//step1. 출발점으로 부터 가장 거리가 짧은 거리 구하기
			int minVertex = -1;
			int minDis = Integer.MAX_VALUE;
			for(int j = 1; j <= V; j++) {
				if(!vis[j] && minDis > dis[j]){
					minDis = dis[j];
					minVertex = j;
				}
			}
//			System.out.println("minver : " + minVertex);
			if(minVertex != -1) vis[minVertex] = true;
			else continue;
			//step2. 뽑힌 점을 연결점으로 갈 수 있는 정점들의 거리 고려하기
			for(int j = 1; j <= V; j ++) {
				if(!vis[j] && map[minVertex][j] != 0 && dis[j] > dis[minVertex] + map[minVertex][j]) {
					dis[j] = dis[minVertex] + map[minVertex][j];
				}
			}
		}
		for(int i = 1; i <= V; i++) {
			if(dis[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(dis[i]);
		}
		
	}
}

우선순위 큐 사용한 코드

package Baekjoon;

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

public class Main_1753_최단경로 {
	static class Node implements Comparable<Node>{
		int to;
		int weight;
		
		public Node(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight; //오름차순
		}
	}

	private static ArrayList<Node>[]  list;
	private static int V, E, K;
	private static int[] dis;
	static final int INF = Integer.MAX_VALUE; 

	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());//간선 수
		st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());//시작 정점
		
		//연결리스트 : ArrayList를 원소로하는 배열 생성
		list = new ArrayList[V+1];
		for(int i = 1; i <= V; i++) {
			list[i] = new ArrayList<>();
		}

		dis = new int[V+1];//최소 거리 배열
		Arrays.fill(dis, INF);//INF로 초기화
		
		
		for(int i =0 ; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list[start].add(new Node(end, w));//start정점에 연결된 정점을 각 정점의 ArrayList에 삽입한다.
		}
		
		dijkstra(K);
		
		
		for(int i = 1; i <= V; i++) {
			if(dis[i] == INF) System.out.println("INF");
			else System.out.println(dis[i]);
		}
		
	}

	private static void dijkstra(int start) {
		dis[start] = 0;
		boolean vis[] = new boolean[V+1];
//		주의: vis[start] = true; => 여기서 시작점을 먼저 체크하면 안됨
		//pQ는 Node를 원소로 하는데 list에서의 Node와 달리 여기서 Node는
		//"start"에서 to정점까지 가는 weight 비용을 의미한다. 
		PriorityQueue<Node> pQ = new PriorityQueue<>();
		pQ.add(new Node(start, 0));
		
		while(!pQ.isEmpty()) {
			//step1. 출발점으로 부터 가장 거리가 짧은 정점 구하기
			//"start"에서 to정점까지 가는 weight비용이 가장 작은 node를 꺼낸다. 
			Node node = pQ.poll();
			int cur = node.to;

			//step2. 방문 체크 
			if(vis[cur]) continue; //이미 방문했던 정점이라면 pass
			vis[cur] = true;//방문체크

			//step3. 뽑힌 점을 연결점으로 갈 수 있는 정점들의 거리 고려하기
			for(Node tmp : list[cur]) {
				//해당 정점과 연결된 정점들 고려해서 dis배열 갱신하기
				//start에서 tmp 정점까지 가는 기존의 거리 > cur정점까지 오는 거리 + cur에서 tmp 정점으로 가는  비용
				if(!vis[tmp.to] && dis[tmp.to] > dis[cur] + tmp.weight) {
					dis[tmp.to] = dis[cur] + tmp.weight;
					pQ.add(new Node(tmp.to, dis[tmp.to]));
				}
			}
			
		}
	}
}