코딩 테스트 대비: 다익스트라 알고리즘을 이용한 최단 경로 찾기 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 다익스트라 알고리즘을 사용하여 최단 경로를 찾는 방법을 다루겠습니다. 다익스트라 알고리즘은 그래프에서 주어진 시작점에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 가진 간선이 없는 그래프에서 사용할 수 있습니다.

 

문제
주어진 가중치가 있는 방향 그래프에서, 시작 정점에서 목표 정점까지의 최단 경로를 찾으세요.

 

예시:

그래프:
A --5--> B --2--> D
 \       ^       v
  3      |       1
   \____>C<______/

시작 정점: A, 목표 정점: D

결과: A -> C -> D (최단 경로 길이: 4)

 

풀이
다익스트라 알고리즘을 사용하여 문제를 해결할 수 있습니다. 다음은 다익스트라 알고리즘의 개략적인 과정입니다.

1. 시작 정점에서 가장 가까운 정점을 선택합니다.
2. 선택한 정점을 통해 이어진 정점들의 거리를 업데이트합니다.
3. 업데이트된 정점 중 가장 가까운 정점을 선택하고 2번 과정을 반복합니다.
4. 모든 정점을 방문할 때까지 이 과정을 반복합니다.

 

먼저, 다익스트라 알고리즘을 구현한 클래스를 작성해보겠습니다.

 

public class Dijkstra {
    private int _vertices;
    private int[,] _adjacencyMatrix;
    private int[] _distances;
    private bool[] _visited;
    private int _start;

    public Dijkstra(int vertices, int[,] adjacencyMatrix, int start) {
        _vertices = vertices;
        _adjacencyMatrix = adjacencyMatrix;
        _distances = Enumerable.Repeat(int.MaxValue, vertices).ToArray();
        _visited = new bool[vertices];
        _start = start;
    }

    public int[] FindShortestPath() {
        _distances[_start] = 0;

        for (int i = 0; i < _vertices - 1; i++) {
            int u = FindNextVertex();
            _visited[u] = true;

            for (int v = 0; v < _vertices; v++) {
                if (!_visited[v] && _adjacencyMatrix[u, v] != 0 && _distances[u] != int.MaxValue &&
                    _distances[u] + _adjacencyMatrix[u, v] < _distances[v]) {
                    _distances[v] = _distances[u] + _adjacencyMatrix[u, v];
                }
            }
        }

        return _distances;
    }

    private int FindNextVertex() {
        int min = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < _vertices; v++) {
            if (!_visited[v] && _distances[v] <= min) {
                min = _distances[v];
                minIndex = v;
            }
        }

        return minIndex;
    }
}

 

이제 주어진 그래프와 시작 정점에 대해 다익스트라 알고리즘을 적용하여 최단 경로를 찾아보겠습니다.

 

public static void Main(string[] args) {
    int[,] adjacencyMatrix = {
        { 0, 5, 3, 0 },
        { 0, 0, 0, 2 },
        { 0, 1, 0, 0 },
        { 0, 0, 0, 0 }
    };

    int start = 0; // 시작 정점: A
    int target = 3; // 목표 정점: D

    Dijkstra dijkstra = new Dijkstra(4, adjacencyMatrix, start);
    int[] shortestPaths = dijkstra.FindShortestPath();

    Console.WriteLine($"최단 경로 길이: {shortestPaths[target]}");
}

 

위 예제에서는 주어진 그래프와 시작 정점 A에 대해 다익스트라 알고리즘을 적용하여 목표 정점 D까지의 최단 경로를 찾았습니다. 실행 결과, 최단 경로 길이가 4로 출력됩니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 다익스트라 알고리즘은 그래프 문제에서 최단 경로를 찾는 데 자주 사용되므로, 꼭 숙지하시기 바랍니다. 다음 포스팅에서도 더 다양한 유형의 문제와 알고리즘에 대해 알아보겠습니다. 게임 개발, 프로그래밍 언어, 자료 구조와 같은 다양한 주제를 다룰 예정이니 계속 코딩 테스트 대비를 위해 저희 블로그를 참조해 주시기 바랍니다.