문제

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

---

입력

첫 줄에 N과 M이 입력된다. N은 정점의 개수이고 M은 도로의 수이다.
다음 줄부터 M개의 줄에 도로의 정보가 입력된다.

---

출력

적당한 도로하나를 파괴했을 때 1번 정점에서 N번 정점으로의 최단거리의 최댓값을 출력한다.

---

풀이

제한조건

• (1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N-1)/2)
• (1 ≤ xi, yi ≤ N, 1 ≤ zi ≤ 1000)

접근방법

단순 탐색 X
경로 중 1개의 간선을 지우고 최단거리를 구해야 한다.
단순히 임의의 1개를 지우고 탐색을 수행해보는 방식을 사용한다면,
시간초과가 날 것이다.
M은 최대 약 500,000개로, 시간 안에 풀 수 없다.

시간을 줄일 수 있는 방법이 어떤것이 있는지 생각해보자.
우선 최단거리를 구하므로, 다익스트라 알고리즘을 떠올려야 한다.

임의의 1개의 간선을 지우고, 최단거리가 최대가 되는 값을 구해야 하므로,
1->N의 최단 경로 상에 있는 간선 1개를 지워야 함을 유추할 수 있다.

최단거리로 이동한 경로의 간선 중 임의의 1개를 지우지 않는 경우,
최단거리는 변하지 않는다.

따라서 다익스트라를 통한 최단거리 + 경로 Trace가 필요함을 알 수 있다.

다익스트라 O
우선 예제의 입력을 그림으로 확인해보자.

input
5 6
1 2 4
1 3 3
2 3 1
2 4 4
2 5 7
4 5 1

최단 경로는 1->2->4->5 또는 1->3->2->4->5 중에 발생하게 된다.
그럼 코드로 이 최단경로를 어떻게 구할 수 있는가하는 문제가 생긴다.
바로 Dijkstra를 수행하는 과정에서 최솟값이 갱신될 때, 기록해주면 된다.

int[] prev; // 경로 Tracing을 위함.
while (!pq.isEmpty()) {
			Node cur = pq.poll();
			if (cur.to == end)
				break;
			for (Node next : graph[cur.to]) {
				if (dist[next.to] > next.weight + dist[cur.to]) {
					dist[next.to] = next.weight + dist[cur.to];
					pq.add(new Node(next.to, dist[next.to]));
					prev[next.to] = cur.to; // 경로 기록
                    // 다음 번호(next.to)로 가기직전 현재 번호(cur.to)를 지난다.
				}
			}
		}

이제 최단거리를 구하는 과정 속에서 어떤 경로를 지나는지 모두 파악했다.
해당 경로들을 하나씩 제외하며 다시 Dijkstra를 수행하며, 최단거리를 구해보면 된다.

고민

다익스트라를 수행하는 과정에서 2가지 고민 항목이 있었음.
그래봤자 알고리즘 푸는건데 해결에만 초점을 두는것도 방법이지만..
최소한의 양심이랄까..
최단거리, 경로 기록, 못가는 경로 처리 3가지 작업이 동일한 다익스트라 알고리즘을 수행하는데 dijk1(), dijk2() .. 이런식으로 구현하기 싫었다.

오버로딩을 통해서 1개로 처리는 했지만,

• 함수에 flag를 주고 if문에 따라 추가적인 작업을 수행하는 것.
• 매개변수가 많은 것.
  이 매우 불편.

---

코드

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

public class Main {
	static class Node implements Comparable<Node> {
		int to;
		int weight;

		Node(int a, int b) {
			to = a;
			weight = b;
		}

		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
	}

	static int N, M;
	static List<Node>[] graph;
	static int[] dist, prev;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = in.readLine().split(" ");

		N = stoi(inputs[0]);
		M = stoi(inputs[1]);

		graph = new List[N + 1];
		for (int i = 0; i <= N; ++i)
			graph[i] = new ArrayList<>();

		for (int i = 0; i < M; ++i) {
			inputs = in.readLine().split(" ");
			graph[stoi(inputs[0])].add(new Node(stoi(inputs[1]), stoi(inputs[2])));
			graph[stoi(inputs[1])].add(new Node(stoi(inputs[0]), stoi(inputs[2])));
		}

		dist = new int[N + 1];
		prev = new int[N + 1];
		prev[0] = -1;
		dijkstra(1, N, true);

		int max = dist[N];
		int end = prev[N];
		int start = N;
		while (start != -1) {
			dijkstra(1, N, false, new int[] {end, start});
			max = Math.max(max, dist[N]);
			end = start;
			start = prev[start];
		}
		System.out.println(max);
	}

	private static void dijkstra(int start, int end, boolean write, int[] pos) {
		Arrays.fill(dist, 123456789);
		dist[start] = 0;
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));

		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			if (cur.to == end)
				break;
			for (Node next : graph[cur.to]) {
				if ((cur.to == pos[0] && next.to == pos[1]) || (cur.to == pos[1] && next.to == pos[0]))
					continue;
				if (dist[next.to] > next.weight + dist[cur.to]) {
					dist[next.to] = next.weight + dist[cur.to];
					pq.add(new Node(next.to, dist[next.to]));
					if (write)
						prev[next.to] = cur.to;
				}
			}
		}
	}

	private static void dijkstra(int start, int end, boolean write) {
		dijkstra(start, end, write, new int[] {-1, -1});
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}