백준 1238번
https://www.acmicpc.net/problem/1238

문제

---

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

생각하기

---

최단 거리를 구하는 간단한 다익스트라 문제였다.
한 가지 특이점이라면, 다시 돌아오는 거리도 구해야 한다는 것이다.

근데, 생각해보면 돌아오는데도 최단 거리를 구하면 되기 때문에, 그냥 단순하게 다익스트라 알고리즘을 학생 한명당 2번씩 실행하면 정답을 구할 수 있다.
이게 내가 생각한 알고리즘이다.

문제를 풀고 나서 다른 분들이 제출한 코드의 효율성에서 너무 비효율적이라는 것을 알게되었다.
그래서 다른 분들의 코드를 보고 학습한 결과 학생 전체를 탐색할 필요없이 전체를 탐색후, 최대값만 추출하면 되서 사실상 다익스트라는 2번만 돌리면 정답을 찾을 수 있었다.

내가 만든 코드는 학생 한명당 최소 거리를 구하기 위해서 다익스트라 알고리즘을 2번씩 실행해서 시간이 많이 걸렸다.

수정 전과 수정 후의 코드가 확연하게 차이가 나니 꼭 차이점을 확인해 보는 것이 좋을 것 같다.

동작

	private static final int INF = Integer.MAX_VALUE;
	static List<ArrayList<Node>> list = new ArrayList<>();
	static List<ArrayList<Node>> backlist = new ArrayList<>();

X 마을로 출발하는 인접리스트와 다시 돌아오는 인접리스트 2개를 생성한다.

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

최소값비교를 위해서 우선순위큐를 사용하는데, 우선순위의 값 비교를 위해 compareTo메소드를 오버라이딩해준다.

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());

			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			list.get(n).add(new Node(m, t));
			backlist.get(m).add(new Node(n, t));
		}

		int max = Integer.MIN_VALUE;

		int goResult[] = dijkstra(list);
		int backResult[] = dijkstra(backlist);

출발하는 인접리스트 list를 만들어주고, 반대로 돌아오는 것을 출발점으로 삼는 backlist의 인접리스트를 2개 만들어주면, 단 2번의 다익스트라 탐색으로 찾을 수 있다.

수정 전의 코드도 문제없이 돌아갔지만, 효율성 측면에서는 확실히 뒤 떨어진다.

코드

---

수정 전.

import java.util.*;
import java.io.*;

public class Main {
	private static final int INF = Integer.MAX_VALUE;
	static List<ArrayList<Node>> list = new ArrayList<>();
	static int N, M, X;

	static class Node implements Comparable<Node> {
		int roadNum; // 도로 번호
		int time; // 시간

		public Node(int roadNum, int time) {
			this.roadNum = roadNum;
			this.time = time;
		}

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

	} // End Node class

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken()); // 
		X = Integer.parseInt(st.nextToken()); // 이동 시간

		list = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<>());
		}

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
	
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			list.get(n).add(new Node(m, t));
		}

		int max = Integer.MIN_VALUE;
		for(int i=1; i<=N; i++) {

			if(i == X) {
				continue;
			}

			int goResult = dijkstra(i, X);
			int backResult = dijkstra(X, i);

			max = Math.max(max, goResult + backResult);
		}

		System.out.println(max);
	} // End of main

	static int dijkstra(int start, int End) {
		PriorityQueue<Node> que = new PriorityQueue<>();		

		boolean visit[] = new boolean[N + 1];
		int dist[] = new int[N + 1];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		que.offer(new Node(start, 0));

		while( !que.isEmpty() ) {
			Node queNode = que.poll();
			int num = queNode.roadNum;

			if( !visit[num] ) {
				visit[num] = true;

				for(Node node : list.get(num)) {
					if( !visit[node.roadNum] && dist[node.roadNum] > (dist[num] + node.time)  ) {
						dist[node.roadNum] = dist[num] + node.time;
						que.offer(new Node(node.roadNum, dist[node.roadNum]));
					}
				}
			}

		}

		return dist[End];
	} // End of dijkstra
} // End of Main class

수정 후.

import java.util.*;
import java.io.*;

public class Main {
	private static final int INF = Integer.MAX_VALUE;
	static List<ArrayList<Node>> list = new ArrayList<>();
	static List<ArrayList<Node>> backlist = new ArrayList<>();
	static int N, M, X;

	static class Node implements Comparable<Node> {
		int roadNum; // 도로 번호
		int time; // 시간

		public Node(int roadNum, int time) {
			this.roadNum = roadNum;
			this.time = time;
		}

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

	} // End Node class

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken()); // 
		X = Integer.parseInt(st.nextToken()); // 이동 시간

		list = new ArrayList<>();
		backlist = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<>());
			backlist.add(new ArrayList<>());
		}

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());

			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			list.get(n).add(new Node(m, t));
			backlist.get(m).add(new Node(n, t));
		}

		int max = Integer.MIN_VALUE;

		int goResult[] = dijkstra(list);
		int backResult[] = dijkstra(backlist);

		for(int i=1; i<=N; i++) {
			max = Math.max(max,  goResult[i] + backResult[i]);
		}

		System.out.println(max);
	} // End of main


	static int[] dijkstra(List<ArrayList<Node>> list) {
		PriorityQueue<Node> que = new PriorityQueue<>();	

		boolean visit[] = new boolean[N + 1];
		int dist[] = new int[N + 1];
		Arrays.fill(dist, INF);
		dist[X] = 0;

		que.offer(new Node(X, 0));

		while( !que.isEmpty() ) {
			Node queNode = que.poll();
			int num = queNode.roadNum;

			if(visit[num]) continue;

			visit[num] = true;
			for(Node node : list.get(num)) {
				if( !visit[node.roadNum] && dist[node.roadNum] > (dist[num] + node.time)  ) {
					dist[node.roadNum] = dist[num] + node.time;
					que.offer(new Node(node.roadNum, dist[node.roadNum]));
				}
			}

		}

		return dist;
	} // End of dijkstra
} // End of Main class