[이것이 코딩테스트다] 8. 최단 경로

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

 

1. 최단 경로(Shortest Path)

- 말 그대로 가장 짧은 경로를 찾는 알고리즘. 

- 최단 경로 문제는 보통 그래프를 이용해 표현하며, 각 지점은 노드로 표현되고 지점 간 연결된 도로는 간선으로 표현

- 코딩테스트에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형이 자주 등장

 

 

2. 다익스트라(Dijkstra) 최단 경로 알고리즘

- 그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘.

- 이 알고리즘은 '음의 간선'(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작하며, 현실 세계 또한 음의 간선으로 표현되지 않아 GPS 의 기본 알고리즘으로 채택되기도 함

- 기본적으로 그리디 알고리즘으로 분류 → 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복

- 원리

1. 출발 노드 설정
2. 최단 거리를 기록할 테이블 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 위 과정의 3번과 4번을 반복

- 구현

예시 그래프

1. 출발 노드 설정 : 1번 노드 선택
2. 최단 거리를 기록할 테이블 초기화 : 다른 모든 노드로 가는 최단 거리를 '무한' or 999999999와 같은 수로 초기화 (출발노드 자신 노드는 0으로 표시)

   노드번호	1	2	3	4	5
   거리	0	무한	무한	무한	무한

3. 1번 노드와 연결된 간선 확인 후 최단 거리 기록 테이블에 갱신 ('무한'보다 짧으므로 갱신)

   노드번호	1	2	3	4	5
   거리	0	1	2	무한	3

4. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 2번 노드 선택하고 (2번 노드까지의 거리 + 2번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신

   노드번호	1	2	3	4	5
   거리	0	1	2	7	3

5. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 3번 노드 선택하고 (3번 노드까지의 거리+ 3번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신

   노드번호	1	2	3	4	5
   거리	0	1	2	7	3

6. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 5번 노드 선택하고 (5번 노드까지의 거리+ 5번 노드에서 다른 노드로 가는 거리)가 테이블의 거리보다 작다면 최단 거리 기록 테이블 갱신

   노드번호	1	2	3	4	5
   거리	0	1	2	7	3

7. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드, 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(N³)

- 디익스트라 알고리즘과는 다르게 다이나믹 프로그래밍으로 볼 수 있음

- 점화식 : D_ab = min(D_ab, D_ak + D_kb)

   → 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

 

다음 장에서는 실전 문제로 포스팅하겠습니다.

 

감사합니다.