Algorithm
[이것이 코딩테스트다] 8. 최단 경로
멍목
2022. 1. 31. 00:39
반응형
이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.
1. 최단 경로(Shortest Path)
- 말 그대로 가장 짧은 경로를 찾는 알고리즘.
- 최단 경로 문제는 보통 그래프를 이용해 표현하며, 각 지점은 노드로 표현되고 지점 간 연결된 도로는 간선으로 표현
- 코딩테스트에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형이 자주 등장
2. 다익스트라(Dijkstra) 최단 경로 알고리즘
- 그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘.
- 이 알고리즘은 '음의 간선'(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작하며, 현실 세계 또한 음의 간선으로 표현되지 않아 GPS 의 기본 알고리즘으로 채택되기도 함
- 기본적으로 그리디 알고리즘으로 분류 → 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복
- 원리
- 출발 노드 설정
- 최단 거리를 기록할 테이블 초기화
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 위 과정의 3번과 4번을 반복
- 구현
- 출발 노드 설정 : 1번 노드 선택
- 최단 거리를 기록할 테이블 초기화 : 다른 모든 노드로 가는 최단 거리를 '무한' or 999999999와 같은 수로 초기화 (출발노드 자신 노드는 0으로 표시)
노드번호 1 2 3 4 5 거리 0 무한 무한 무한 무한 - 1번 노드와 연결된 간선 확인 후 최단 거리 기록 테이블에 갱신 ('무한'보다 짧으므로 갱신)
노드번호 1 2 3 4 5 거리 0 1 2 무한 3 - 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 2번 노드 선택하고 (2번 노드까지의 거리 + 2번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신
노드번호 1 2 3 4 5 거리 0 1 2 7 3 - 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 3번 노드 선택하고 (3번 노드까지의 거리+ 3번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신
노드번호 1 2 3 4 5 거리 0 1 2 7 3 - 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 5번 노드 선택하고 (5번 노드까지의 거리+ 5번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신
노드번호 1 2 3 4 5 거리 0 1 2 7 3 - 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 4번 노드 선택하고 (4번 노드까지의 거리+ 4번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신
노드번호 1 2 3 4 5 거리 0 1 2 7 3
- 이 테이블은 1번 노드에서 각 노드까지의 최단 경로를 나타내는 것.
• 구현 방법 1 : 난이도↓ 성능↓
- 시간복잡도 : O(V2) (V : 노드의 갯수)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class simple_dijkstra {
// 무한을 의미하는 값으로 10억 설정
public static final int INF = (int) 1e9;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
public static int n, m, start;
// 그래프 변수
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 방문 체크용 변수 생성
public static boolean[] visited;
// 최단 거리 테이블 만들기
public static int[] d;
// 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드 반환
public static int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
public static void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
// 시작 노드도 방문 체크
visited[start] = true;
// 시작노드와 연결된 간선 갱신
// if로 비교하지 않는 이유? 초기에 기록용 변수에 다 무한으로 저장해놨기 때문에 거리가 있다면 무한보다 작을 수 밖에 없다.
for (int i = 0; i < graph.get(start).size(); i++) {
d[graph.get(start).get(i).getIndex()] = graph.get(start).get(i).getDistance();
}
// 시작 노드를 제외한 노드 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph.get(now).size(); j++) {
int cost = d[now] + graph.get(now).get(j).getDistance();
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우에만 갱신
if (cost < d[graph.get(now).get(j).getIndex()]) {
d[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}
public static void main(String[] args) throws IOException{
// 입력이 빠른 BufferedReader 이용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 공백을 구분하여 반환해주는 StringTokenizer 이용
StringTokenizer st = new StringTokenizer(br.readLine());
// 노드의 갯수(n), 간선의 갯수(m), 시작 노드(start) 입력
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
// 방문 체크용 변수와 최단 경로 기록용 변수에 크기 할당
visited = new boolean[n+1];
d = new int[n+1];
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
// from 노드에서 to노드로 가는 비용이 cost
graph.get(from).add(new Node(to, cost));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, '갈 수 없음' 출력
if (d[i] == INF) {
System.out.println(i+"번 노드 까지의 최단 거리 : 갈 수 없음");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(i+"번 노드 까지의 최단 거리 : " + d[i]);
}
}
}
}| 입력 | 출력 |
| 5 9 1 1 2 1 1 3 2 1 5 3 2 3 2 2 4 6 3 1 4 3 4 5 4 5 2 4 2 3 |
1번 노드 까지의 최단 거리 : 0 2번 노드 까지의 최단 거리 : 1 3번 노드 까지의 최단 거리 : 2 4번 노드 까지의 최단 거리 : 7 5번 노드 까지의 최단 거리 : 3 |
• 구현 방법 2 : 난이도↑ 성능↑
- 시간복잡도 : O(ElogV) (V : 노드의 갯수, E : 간선의 갯수)
- Heap 자료구조 이용 (모든 원소를 저장한 후, 우선순위에 맞게 빠르게 뽑아낼 수 있는 '우선순위 큐'에 사용)
→ 구현 방법1에서 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 추가로 이용.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
//거리와 노드를 저장할 수 있는 Node Class 선언
class Node implements Comparable<Node>{
// 거리
private int distance;
// 노드
private int index;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getDistance() {
return this.distance;
}
public int getIndex() {
return this.index;
}
// 거리가 낮을수록 우선순위가 높게 설정
@Override
public int compareTo(Node other) {
if(this.distance < other.distance) {
return -1;
}else {
return 1;
}
}
}
public class Main {
// 무한을 의미하는 10억, INF라는 파이널 상수 선언
public static final int INF = (int)1e9;
// 노드의 갯수 : N
// 간선의 갯수 : M
// 시작점 노드 : start
public static int N,M,start;
// 노드와 간선의 정보를 가지는 그래프 변수
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 최단 거리를 저장할 변수
// 노드는 최대 100000개라고 가정
public static int[] d;
public static void dijkstra() {
// 우선순위 큐 선언
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작노드. 즉, 자기 자신의 거리는 0으로 설정
pq.offer(new Node(start, 0));
d[start] = 0;
// 우선순위 큐가 빌 때까지 반복
while(!pq.isEmpty()) {
// 최단 거리가 가장 짧은 노드 꺼내기
// 우선순위 큐이기에 알아서 꺼내짐
Node node = pq.poll();
// 시작 노드에서 현재 노드까지의 거리 합
int distance = node.getDistance();
// 현재 노드
int index = node.getIndex();
// 현재 노드가 처리된 적이 있는 경우
// 조건처럼 큐의 거리가 더 작은 경우는 이전에 큐에 들어가고, 그 이후에 더 짧은 경로를 찾아 갱신했다는 뜻
// continue를 이용해 무시
if(d[index] < distance) {
continue;
}
// 현재 노드와 연결된 다른 노드와의 거리 확인
for(int i=0; i < graph.get(index).size(); i++) {
int cost = distance + graph.get(index).get(i).getDistance();
// 현재의 노드를 경유하여 i번째 노드로 가는 것이 최단 경로에 기록된 거리보다 효율적일 때 갱신 및 우선순위 큐에 해당 노드의 정보를 삽입
if(cost < d[graph.get(index).get(i).getIndex()]) {
d[graph.get(index).get(i).getIndex()] = cost;
pq.offer(new Node(graph.get(index).get(i).getIndex(), cost));
}
}
}
}
public static void main(String[] args) throws IOException{
// 입력기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 공백을 기준으로 문자를 분리해주는 함수
StringTokenizer st = new StringTokenizer(br.readLine());
// 노드의 갯수 입력
N = Integer.parseInt(st.nextToken());
// 간선의 갯수 입력
M = Integer.parseInt(st.nextToken());
// 시작점 노드 설정
start = Integer.parseInt(br.readLine());
// 최단 거리를 저장할 변수. 노드의 갯수+1만큼 공간 할당
d = new int[N+1];
// 노드의 갯수만큼 그래프에 노드 추가
// 보기 쉽게 하기위해, 0번부터 N번을 포함하여 생성
// 0은 사용 X
for(int i=0; i<=N; i++) {
graph.add(new ArrayList<Node>());
}
// 간선의 갯수만큼 반복 및 간선 데이터 저장
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
// 그래프 변수에 넣어주기
// from노드에서 to노드까지의 distance거리
graph.get(from).add(new Node(to, distance));
}
// 최단 경로 변수에 모든 노드에 대한 거리를 INF로 초기화
Arrays.fill(d, INF);
// 최단 경로 확인
dijkstra();
// 시작 노드에서 각 노드별 최단 경로 출력
for(int i=1; i<=N; i++) {
System.out.print(i+"번 노드까지의 거리 : ");
// 갈 수 없는 경우 무한으로 출력
if(d[i] == INF) {
System.out.println("갈 수 없음");
}
else {
System.out.println(d[i]);
}
}
}
}| 입력 | 출력 |
| 5 9 1 1 2 1 1 3 2 1 5 3 2 3 2 2 4 6 3 1 4 3 4 5 4 5 2 4 2 3 |
1번 노드 까지의 최단 거리 : 0 2번 노드 까지의 최단 거리 : 1 3번 노드 까지의 최단 거리 : 2 4번 노드 까지의 최단 거리 : 7 5번 노드 까지의 최단 거리 : 3 |
3. 플로이드 워셜 알고리즘(Floyd-warshall Algorithm)
- '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용 가능
- 시간복잡도 : O(N3)
- 디익스트라 알고리즘과는 다르게 다이나믹 프로그래밍으로 볼 수 있음
- 점화식 : Dab = min(Dab, Dak + Dkb)
→ a에서 b로가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은 지 검사
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// 무한 변수 선언
public static final int INF = (int)1e9;
// 노드의 갯수 : N
// 간선의 갯수 : M
public static int N,M;
// 2차원 배열로 그래프 표현
// 노드의 최대 갯수를 500개로 가정
public static int[][] graph;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 노드의 갯수 입력받기
N = Integer.parseInt(br.readLine());
graph = new int[N+1][N+1];
// 간선의 갯수 입력받기
M = Integer.parseInt(br.readLine());
// 최단 거리 테이블을 무한으로 초기화
for(int i=0; i<N+1; i++) {
Arrays.fill(graph[i], INF);
}
// 자기 자신으로의 거리는 0으로 초기화
for(int i=1; i<=N; i++) {
graph[i][i] = 0;
}
// 그래프 데이터 설정
for(int i=0; i<M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
graph[from][to] = distance;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= N; k++) {
for (int from = 1; from <= N; from++) {
for (int to = 1; to <= N; to++) {
graph[from][to] = Math.min(graph[from][to], graph[from][k] + graph[k][to]);
}
}
}
// 수행된 결과를 출력
for (int a = 1; a <= N; a++) {
for (int b = 1; b <= N; b++) {
// 갈 수 없는 경우, X이라고 출력
if (graph[a][b] == INF) {
System.out.print("X ");
}
// 갈 수 있는 경우 최단 경로 출력
else {
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
}| 입력 | 출력 |
| 5 9 1 2 1 1 3 2 1 5 3 2 3 2 2 4 6 3 1 4 3 4 5 4 5 2 4 2 3 |
0 1 2 7 3 6 0 2 6 8 4 5 0 5 7 9 3 5 0 2 X X X X 0 |
다음 장에서는 실전 문제로 포스팅하겠습니다.
감사합니다.
반응형