greentea31's Note

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

풀이 과정

어떤 도시에서 출발해, 도착지점까지 버스를 타고 가는 최소 비용을 구하고, 그 경로를 출력하는 문제이다.

음수 가중치가 존재하지 않는, 가중치가 존재하는 그래프에서의 최소 비용을 구하는 문제이므로 다익스트라 알고리즘을 활용해서 문제를 해결할 수 있다. 우선순위 큐를 활용한 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이므로 TLE도 발생하지 않음을 확인할 수 있다.

다익스트라 알고리즘 진행 도중, 다음 정점까지 가는 비용이 현재 정점을 경유하는 경우가 더 저렴하면, pre[nxt] = cur로 nxt 정점을 최소 비용으로 방문하기 위해서는 이전 정점으로 cur 정점을 거쳐야 한다는 점을 표시해주자. 그렇다면 end까지 도착했을때, end부터 계속 pre 배열을 확인하면 start부터 end까지 최소비용으로 방문했을 때의 경로를 역순으로 얻어낼 수 있으며, 이를 다시 뒤집어서 출력하면 경로를 반환할 수 있다.

소스 코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 도시의 개수를 입력받는다
		int m = Integer.parseInt(br.readLine()); // 버스의 개수를 입력받는다
		ArrayList<ArrayList<int[]>> al = new ArrayList<>(); // u번째 버스에서 출발하는 (비용, 도착지) 버스 노선을 저장한다
		int[] d = new int[n+1]; // 시작지로부터의 비용을 저장한다
		int[] pre = new int[n+1]; // 시작지점부터 특정 도시까지 최소비용으로 도달하기 위한 경로의 바로 이전 도시를 저장한다
		
		for (int i = 0; i <= n; i++) {
			al.add(new ArrayList<>()); // 인접 리스트 초기화
			d[i] = Integer.MAX_VALUE; // 시작지로부터의 비용을 MAX로 초기화한다
		}
		
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()); // 출발지 입력
			int v = Integer.parseInt(st.nextToken()); // 도착지 입력
			int w = Integer.parseInt(st.nextToken()); // 비용 입력
			al.get(u).add(new int[] {w, v}); // u번째 버스에서 출발하는 버스들의 리스트에 (비용, 도착지) 삽입
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken()); // 시작지점 입력
		int end = Integer.parseInt(st.nextToken()); // 도착지점 입력
		
		// (비용, 도착지)에서 비용의 오름차순으로 우선순위를 갖는 우선순위 큐 선언
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
		d[start] = 0; // 시작지점까지의 거리는 0
		pq.add(new int[] {d[start], start}); // pq에 가장 거리가 가까운 점을 넣는다
		
		// 다익스트라 진행
		while(!pq.isEmpty()) {
			int[] cur = pq.poll(); // 우선순위 큐에서 하나 빼고
			
			// 뺀 정점까지의 거리가 갱신된 시작정점까지의 거리와 다르면 쓰레기 값이므로 다른 값을 뺀다
			if (cur[0] != d[cur[1]]) continue; 
			
			// 현재 보고 있는 정점에서 경로가 존재하는 모든 도착도시에 대해
			for (int[] nxt : al.get(cur[1])) {
				
				// 도착도시까지의 거리가 현재 보고있는 정점을 거쳐가는게 더 비용이 적은 경우에 갱신한다
				if (d[nxt[1]] <= d[cur[1]] + nxt[0]) continue;
				d[nxt[1]] = d[cur[1]] + nxt[0];
				
				// 그리고 우선순위 큐에 넣는다
				pq.add(new int[] {d[nxt[1]], nxt[1]});
				// 현재 정점을 거쳐가는 것이 nxt까지의 경로중 가장 비용이 적으므로, 저장한다
				pre[nxt[1]] = cur[1];
			}
		}
		
		// 최소 비용을 출력한다
		sb.append(d[end]).append('\n');
		
		// 도착정점부터 pre 배열을 살펴보며 최소 비용으로 순회하는 경로를 역순으로 스택에 삽입한다
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int index = end;
		q.addLast(index);
		
		while (index != start) {
			index = pre[index];
			q.addLast(index);
		}
		
		sb.append(q.size()).append('\n');
		
		// 스택에서 다시 빼면서 출력하면 출발도시에서 도착도시까지의 경로가 출력된다
		while(!q.isEmpty()) {
			sb.append(q.pollLast()).append(' ');
		}
		
		System.out.print(sb.toString());
	}
}

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

풀이 과정

도시와 도시 사이를 운행하는 버스가 있을 때, A번째 도시에서 B번째 도시로 가는 최소비용과 경로를 출력하는 문제이다.

• 음수 간선 없는 최단거리 -> 다익스트라 알고리즘
• 특정 정점 i를 최단거리로 방문하기 위해서 바로 직전 정점으로 j를 방문해야 한다면 pre[i] = j로 표시
• 마지막 정점에서 역추적하면서 최단경로를 역순으로 뽑아낼 수 있으며, 이를 다시 역순으로 출력해주면 된다.

소스 코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException { // 메모리 56776KB 시간 632ms
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<int[]>> al = new ArrayList<>();
		int[] d = new int[n+1];
		int[] pre = new int[n+1];
		
		for (int i = 0; i <= n; i++) {
			al.add(new ArrayList<>());
			d[i] = Integer.MAX_VALUE;
		}
		
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			al.get(u).add(new int[] {w, v});
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
		d[start] = 0;
		pq.add(new int[] {d[start], start});
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			
			if (cur[0] != d[cur[1]]) continue;
			
			for (int[] nxt : al.get(cur[1])) {
				if (d[nxt[1]] <= d[cur[1]] + nxt[0]) continue;
				d[nxt[1]] = d[cur[1]] + nxt[0];
				pq.add(new int[] {d[nxt[1]], nxt[1]});
				
				// nxt를 갈 때 cur를 거쳐가는게 더 빠르다면, pre[nxt] = cur로 설정
				pre[nxt[1]] = cur[1]; 
			}
		}
		
		sb.append(d[end]).append('\n');
		
		
		// 스택을 이용하여 끝에서부터 역추적
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int index = end;
		q.addLast(index);
		
		while (index != start) {
			index = pre[index];
			q.addLast(index);
		}
		
		sb.append(q.size()).append('\n');
		
		// 스택에 넣은 뒤 다시 다 빼면 뒤집어서 나온다
		while(!q.isEmpty()) {
			sb.append(q.pollLast()).append(' ');
		}
		
		System.out.print(sb.toString());
	}
}