[BOJ - 1916, 1753, 11404, 11779] 다익스트라, 플로이드-와샬 개념 제대로 잡기

# 주소

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

1916번: 최소비용 구하기

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

1753번: 최단경로

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

11779번: 최소비용 구하기 2

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

11404번: 플로이드

 

# 문제 해설 및 코드 리뷰

 

이번에는 4개의 문제를 준비했습니다.

이 4개의 문제들만 제대로 푸신다면 다익스트라와 플로이드 와샬에 대한 개념은 확실히 잡히실 수 있습니다.

문제들을 풀다 보면 대부분 공통적인 특징이 있기 때문에 이부분만 잘 캐치하시면 실력 향상에 정말 큰 도움이 됩니다.

먼저 1916번의 최소 비용 구하기 문제부터 살펴봅시다.

# 1916 - 최소 비용 구하기

# 코드

import java.util.*;
class Min{
	int x;
	int dir;
	Min(int x, int dir) {
		this.x = x;
		this.dir = dir;
	}
}
public class Main {
	static int n, m, start, end;
	static List<Min>[] list;
	static int[] arr;
	static boolean[] visit;
	static PriorityQueue<Min> queue;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		list = new List[n + 1];
		visit = new boolean[n + 1];
		queue = new PriorityQueue<Min>((o1, o2) -> (o1.dir - o2.dir));
		for(int i = 0; i < n + 1; i++)
			list[i] = new ArrayList<Min>();
		arr = new int[n + 1];
		for(int i = 0; i < n + 1; i++)
			arr[i] = Integer.MAX_VALUE;
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			list[a].add(new Min(b, c));
		}
		start = scan.nextInt();
		end = scan.nextInt();
		dfs(start, end);
	}
	static void dfs(int x, int y) {
		arr[x] = 0;
		queue.offer(new Min(x, 0));
		while(!queue.isEmpty()) {
			Min now = queue.poll();
			if(visit[now.x])continue;
			visit[now.x] = true; 
			if(now.dir < arr[now.x])continue; 
			for(Min next : list[now.x]) {
				if(arr[next.x] > now.dir + next.dir) {
					arr[next.x] = now.dir + next.dir;
					queue.offer(new Min(next.x, arr[next.x]));
				}
			}
		}
		System.out.println(arr[y]);
	}

}

말 그대로 최소 비용을 출력하는 문제입니다.

다익스트라의 문제는 다른 그래프 탐색 문제와는 다른 특징이 있습니다.

바로 "우선 순위 큐"를 기본적으로 다룰줄 알아야 한다는 것입니다.

다익스트라는 기본적으로 

"최초의 출발 노드를 기준으로 갈 수 있는 주변 인덱스 노드들 마다 모든 비용을 계산 후 가장 최소의 비용이 드는 간선부터 우선적으로 정렬한 후 이동합니다. 이후 최초에 탐색한 노드는 더 이상 방문하지 않아도 되므로 visit처리한 후 (BFS와 다른 점이 바로 이 부분입니다. BFS는 주변에 노드가 있으면 그 노드를 방문처리하지만, 다익스트라는 인근 노드를 모두 탐색 후 원래의 노드를 방문처리합니다."

이해가 안되신다면 5번, 10번도 더 읽어보셔야 합니다.

왜 다익스트라는 방문할때마다 VISIT하는 것이 아니라, 방문을 다 하고 나서 ORIGIN 노드를 방문처리할까요?

그 이유는 꽤나 간단합니다.

이후에 방문할 수 있는 노드에 의해 비용이 최솟값으로 갱신될 수 있기 때문에 그렇습니다.

제가 우선순위 큐를 사용한다고 해서, 큐에 노드가 한 개씩 들어간다고 생각하시면 큰 오산입니다.

결국 다익스트라 알고리즘도 BFS처럼 인근의 노드를 탐색해야 하기 때문에, 인근 노드 개수만큼 일단은 큐에 넣어줘야 하기 때문에 그렇습니다.

즉, "QUEUE에 한 개씩 들어가서 최솟값만 찾아다니는 것이 아니라, 간선의 비용이 최소인 것부터 우선적으로 인근 노드를 탐색 후 계속해서 확장해 나간다"라고 이해하시면 되겠습니다.

이걸 알고 난뒤에는 굉장히 다익스트라 문제가 쉽게 여겨지실겁니다.

 

문제를 봅시다.

문제를 보면 출발 도시에서 도착도시까지 비용이 주어지므로 저는 List[]를 사용하겠습니다.

무턱대고 arr[][] 이걸 쓰시는 분도 계시는데 시간 복잡도 면에서 쓸데없는 탐색을 하게되어 List[]가 낫습니다.

queue = new PriorityQueue<Min>((o1, o2) -> (o1.dir - o2.dir));
		for(int i = 0; i < n + 1; i++)
			list[i] = new ArrayList<Min>();
		arr = new int[n + 1];
		for(int i = 0; i < n + 1; i++)
			arr[i] = Integer.MAX_VALUE;
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			list[a].add(new Min(b, c));
		}

따라서 지금 보시면, Queue를 dir의 내림차순에 따라 데이터를 정렬하는걸 알 수 있는데 람다를 이용하여 저렇게 표현할 수도 있답니다.

arr[x] = 0;
		queue.offer(new Min(x, 0));
		while(!queue.isEmpty()) {
			Min now = queue.poll();
			if(visit[now.x])continue;
			visit[now.x] = true; 
			if(now.dir < arr[now.x])continue; 
			for(Min next : list[now.x]) {
				if(arr[next.x] > now.dir + next.dir) {
					arr[next.x] = now.dir + next.dir;
					queue.offer(new Min(next.x, arr[next.x]));
				}
			}
		}

arr는 다익스트라가 DP 계열이기 때문에 배열을 이용하여 최솟값을 저장하기 위해 사용합니다.

아래의 for문을 보시면 arr값이 해당지점보다 더 클 때마다 arr값을 갱신하고 queue에 삽입하는 것을 볼 수 있습니다.

이 때 arr값은 여러번 방문될 수 있기 때문에 visit배열로 섣불리 탐색하지 않는 것입니다.

하지만 반대로 생각하면 원래의 노드는 한 번 탐색한 뒤로 그 지점에서 출발할 수 있는 노드래봤자 재탐색밖에 안되는 것이므로 visit을 true로 바꾸어 주는 것입니다.

이해되시나요?

while문에서 빠져나오면 arr[end]지점을 출력하면 그것이 도착지점의 값이 됩니다.

다익스트라는 이게 다에요.

여기서 조금 더 응용할 수 있습니다.

어떤지 보겠습니다.

 

# 최소 비용 구하기 2

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

11779번: 최소비용 구하기 2

import java.util.*;
class Cost{
	int x;
	int dir;
	Cost(int x, int dir){
		this.x = x;
		this.dir = dir;
	}
}
public class Main2 {
	static int n, m, start, end;
	static int[] arr, map;
	static boolean[] visit;
	static List<Cost>[] list;
	static PriorityQueue<Cost> queue;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		list = new List[n + 1];
		arr = new int[n + 1];
		map = new int[n + 1];
		visit = new boolean[n + 1];
		for(int i = 0; i < n + 1; i++)
			arr[i] = 1000000001;
		for(int i = 0; i <= n; i++) 
			list[i] = new ArrayList<Cost>();
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			list[a].add(new Cost(b, c));
		}
		start = scan.nextInt();
		end = scan.nextInt();
		dfs(start, end);
	}
	static void dfs(int x, int y) {
		queue = new PriorityQueue<Cost>((o1, o2) -> (o1.dir - o2.dir));
		arr[x] = 0;
		map[x] = 0;
		queue.offer(new Cost(x, 0));
		while(!queue.isEmpty()) {
			Cost now = queue.poll();
			if(arr[now.x] < now.dir) continue;
			if(visit[now.x])continue;
			visit[now.x] = true;
			for(Cost next : list[now.x]) {
				if(arr[next.x] > now.dir + next.dir) {
					arr[next.x] = now.dir + next.dir;
					queue.offer(new Cost(next.x, arr[next.x]));
					map[next.x] = now.x; 
				}
			}
		}
		ArrayList<Integer> ll = new ArrayList<Integer>();
		while(y != 0) {
			ll.add(y);
			y = map[y];
		}
		System.out.println(arr[end]);
		System.out.println(ll.size());
		for(int i = ll.size() - 1; i >= 0; i--)
			System.out.print(ll.get(i) + " ");
	}
}

이 문제는 시작점에서 끝지점까지 최솟값을 구하는 것은 앞의 문제와 동일합니다.

다만, 경로를 따로 구해주어야 하는데요.

이를 위해서 저는 map이라는 1차원 배열을 한 개 더 사용했습니다.

이 map에는 시작지점의 인덱스들을 모두 담습니다.

그리고 역으로 map에서 0인덱스까지 map을 역추적하여 List에 담고 이를 출력하면 정상적으로, 다익스트라의 경로도 구할 수 있습니다.

아이디어가 어려워서 그렇지 한 번 이해하고 난다면 다 비슷한 메커니즘임을 알 수 있습니다.

또 한 번 봅시다.

 

# 특정한 최단 경로

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

1504번: 특정한 최단 경로

import java.util.*;
class Node{
	int x;
	int dir;
	Node(int x, int dir){
		this.x = x;
		this.dir = dir;
	}
}
class Solution{
	static int n, e, v1, v2;
	static PriorityQueue<Node> queue;
	static int[] map;
	static List<Node>[] list;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		e = scan.nextInt();
		map = new int[n + 1];
		list = new List[n + 1];
		for(int i = 0; i <= n; i++)
			map[i] = 10000000;
		for(int i = 0; i < n + 1; i++)
			list[i] = new ArrayList<Node>();
		for(int i = 0; i < e; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			list[a].add(new Node(b, c));
			list[b].add(new Node(a, c));
		}
		v1 = scan.nextInt();
		v2 = scan.nextInt();
		int path1 = dfs(1, v1) + dfs(v1, v2) + dfs(v2, n);
		int path2 = dfs(1, v2) + dfs(v2, v1) + dfs(v1, n);
		int answer = Math.min(path1, path2);
		if(answer >= 10000000) System.out.println(-1);
		else System.out.println(answer);
	}
	private static int dfs(int x, int end) {
		int[] ans = map.clone();
		queue = new PriorityQueue<>((o1, o2) -> (o1.dir - o2.dir));
		queue.offer(new Node(x, 0));
		ans[x] = 0;
		while(!queue.isEmpty()) {
			Node now = queue.poll();
			if(ans[now.x] < now.dir)
				continue;
			for(Node next : list[now.x]) {
				if(now.dir + next.dir < ans[next.x]) {
					ans[next.x] = now.dir + next.dir;
					queue.offer(new Node(next.x, ans[next.x]));
				}
			}
		}
		return ans[end];
	}
	
}

이 문제는 반드시 v1, v2라는 노드를 거쳐서 1부터 n까지의 최소값을 다익스트라를 이용해서 구해야 하는데요.

처음에 저는 v1, v2를 hashSet에 모두 담고 이게 최솟값인지 보고 아니면 틀리는 식으로 구현하려 했는데요.

위에서 언급드렸듯 DP 계열이기 때문에 arr를 갱신해나가기 때문에 v1, v2가 모두 없을 때 최솟값을 복원시켜야 하는데 어디까지 복원시킬지에 대한 부분은 구현이 어렵기 때문에 다른 방법을 모색해야 했습니다.

이를 위해 1부터 v1, v2, n까지 탐색하는 다익스트라기법과 1부터 v2, v1, n까지 탐색하는 다익스트라 기법값 중 최솟값을 갱신하면 됩니다.

ans를 dfs실행마다 map을 clone하여 사용하는 이유는, 다른 dfs문에 영향을 안주기 위해서입니다.

 

지금까지 다익스트라 문제 쭉 보니 어떻나요?

골드 문제임에도 불구하고 형태가 거의 비슷비슷하단걸 눈치 채셨을 것입니다.

다만 조금 변수가 될 수 있는건 간선이 양방향인지, 단선인지, 비용이 따로 주어지는지 아니면 1로 고정되어 있는지, 또 방문할 수 있는지 아닌지, 최초의 arr배열을 초기화 할 때 얼마로 잡을지 정도만 생각하면 된답니다.

 

마지막으로 플로이드 와샬입니다. 한 문제만 짧게 보겠습니다.

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

11404번: 플로이드

import java.util.*;
public class Main {
	static int n, m;
	static int[][] arr;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		arr = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) continue;
				arr[i][j] = 10000000;
			}
		}
		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			int c = scan.nextInt();
			arr[a][b] = Math.min(c, arr[a][b]);
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				for(int k = 1; k <= n; k++) {
					if(i == j) continue;
					arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(arr[i][j] == 10000000)
					arr[i][j] = 0;
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}
}

딱히 보면 별거 없는 문제입니다.

제일 중요한건, arr를 최초에 잡을 때 Integer.MAX_VALUE로 하시면, 나중에 덧셈할 때 정수형을 초과하기 때문에 음수가 될 수 있으므로 지양해주셔야 합니다.

무작정 큰 수로 잡으시면 안된다고 말씀드리고 싶습니다.

그리고 이 기법의 가장 큰 특징은 3중 for문을 사용한다는 것인데요.

n값이 커지면 다익스트라가 훨씬 좋지만 플로이드만큼 구현이 간단한 것이 없기 때문에 외우셔서 쓰시면 정말 요긴합니다.

저는 어떻게 외웠냐면, 3중 for문에서 i, j, k순서로 변수를 사용하니까, arr[j][k] (2, 3번째)는 arr[j][k]와 arr[j][i] (2, 1번째) + arr[i][k] (1, 3번째) 랑 비교해서 작은 값을 넣으면 됩니다.

진짜 이거면 끝이에요.

이 형태로 arr가 n x m크기 그대로 출력해보시면 i행 j열에 있는 어떤 특정한 값은, i번 노드에서 j번 노드까지 가는 최솟값은 arr[i][j]임을 직접 알 수 있습니다.

얼떨결에 다익스트라 정리하고 싶어서 쭉 풀면서 정리했는데 (제 블로그에 다익스트라가 많이 없더라구요) 도움이 되셨길 바랍니다.

포스팅하기 위해서 이거보다 2배수를 이틀에 걸쳐서 푼거 같은데 꽤 재밌네요 ㅋㅋㅋ