본문 바로가기
Problem Solving/백준

백준 5719 : 거의 최단 경로

by Libi 2021. 6. 30.
반응형

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

 

5719번: 거의 최단 경로

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있

www.acmicpc.net

[ 문제풀이 ]

한 정점에서 다른 한 정점으로 가는 최단 경로를 구하는 것이기 때문에 다익스트라 알고리즘을 사용하면 된다.

초기에는 다익스트라로 최단 경로를 구한 후 최단경로가 갱신될 때까지 간선 제거+다익스트라를 반복하였다. 하지만 최단 경로가 2개 이상인 경우 문제가 발생하였다.

위와 같은 경우 하나의 최단 경로 간선을 제거한다면 두 번째 다익스트라에서 1->4->3의 경로가 존재하게 된다. 하지만 실제로는 1->2, 2->3, 2->4, 4->3, 4개의 간선이 제거되기 때문에 두 번째 다익스트라에서 최단 경로는 존재하지 않는다.

따라서 다익스트라를 반복하지 말고 최단 경로를 리스트로 저장하여 한번에 경로를 제거해준다.

다른 풀이를 살펴보니 경로를 저장해주지 않고도 dp로 역경로를 추적할 수 있다는 것을 알게 되었다.

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

public class Main {

	static class Edge implements Comparable<Edge> {
		int to, cost;

		public Edge(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	static final int INF = (int) 1e9;
	static int N, M, S, D;
	static int[] dist;
	static List<Integer>[] path;
	static List<Edge>[] edgeList;
	static PriorityQueue<Edge> pq;
	static boolean[][] check;

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));) 
		{
			edgeList = new ArrayList[501];
			path = new ArrayList[501];
			dist = new int[501];
			check = new boolean[501][501];
			pq = new PriorityQueue<>();
			for (int i = 0; i < 501; ++i) {
				edgeList[i] = new ArrayList<>();
				path[i] = new ArrayList<>();
			}

			while (true) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				N = Integer.parseInt(st.nextToken());
				M = Integer.parseInt(st.nextToken());
				if (N == 0 && M == 0) break;

				st = new StringTokenizer(br.readLine());
				S = Integer.parseInt(st.nextToken());
				D = Integer.parseInt(st.nextToken());

				for (int i = 0; i < M; ++i) {
					st = new StringTokenizer(br.readLine());
					int U = Integer.parseInt(st.nextToken());
					int V = Integer.parseInt(st.nextToken());
					int P = Integer.parseInt(st.nextToken());
					edgeList[U].add(new Edge(V, P));
				}

				dijkstra();
				removeEdge(D);
				dijkstra();

				bw.write((dist[D] == INF ? -1 : dist[D]) + "\n");

				for (int i = 0; i < N; ++i) {
					edgeList[i].clear();
					path[i].clear();
					Arrays.fill(check[i], false);
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void dijkstra() {
		for (int i = 0; i < N; ++i) {
			dist[i] = INF;
		}

		dist[S] = 0;
		pq.offer(new Edge(S, 0));
		while (!pq.isEmpty()) {
			Edge e = pq.poll();

			if (dist[e.to] < e.cost) continue;

			for (Edge ne : edgeList[e.to]) {
				if (check[e.to][ne.to]) continue;//제거된 간선

				//같은 최단 경로라면 path에 저장
				if (dist[ne.to] == e.cost + ne.cost) {
					path[ne.to].add(e.to);
				} 
				//새로운 최단 경로라면 기존의 path를 제거 후 저장
				else if (dist[ne.to] > e.cost + ne.cost) {
					dist[ne.to] = e.cost + ne.cost;
					path[ne.to].clear();
					path[ne.to].add(e.to);
					pq.offer(new Edge(ne.to, dist[ne.to]));
				}
			}
		}
	}

	public static void removeEdge(int v) {
		for (int bv : path[v]) {
			if (check[bv][v]) continue;
			check[bv][v] = true;
			removeEdge(bv);
		}
	}
}
반응형

'Problem Solving > 백준' 카테고리의 다른 글

백준 2211 : 네트워크 복구  (0) 2021.07.05
백준 1525 : 퍼즐  (0) 2021.07.04
백준 16437 : 양 구출 작전  (0) 2021.07.03
백준 2239 : 스도쿠  (0) 2021.07.01
백준 1593 : 문자 해독  (0) 2021.06.29

댓글