C# 코딩테스트 강좌, 그래프의 표현

작성자: 조광형 | 날짜: [날짜]

서론

코딩 테스트에서 알고리즘은 매우 중요한 역할을 합니다. 특히, 그래프 알고리즘은 문제 해결 능력을 평가하는 데 있어 자주 등장하는 주제 중 하나입니다. 이번 글에서는 C#을 활용하여 그래프를 표현하는 방법과 함께, 그래프를 이용한 알고리즘 문제를 해결하는 과정에 대해 자세히 알아보겠습니다.

그래프란 무엇인가?

그래프는 노드(또는 정점)와 이들 간의 관계를 나타내는 간선으로 구성된 자료구조입니다. 그래프는 두 가지 주요 요소로 나눌 수 있습니다:

정점(Vertices): 그래프의 노드입니다.
간선(Edges): 정점들 간의 연결을 나타냅니다.

그래프는 방향성이 있을 수도 있고(유향 그래프), 없을 수도 있습니다(무향 그래프). 또한 연결 그래프와 비연결 그래프로도 분류될 수 있습니다.

그래프의 표현 방법

그래프를 표현하는 방법은 여러 가지가 있지만, 일반적으로 사용되는 두 가지 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다.

1. 인접 행렬(Adjacency Matrix)

인접 행렬은 그래프의 정점 수에 따라 n x n 크기의 2차원 배열을 사용하여 그래프를 표현합니다. 만약 정점 i와 정점 j가 서로 연결되어 있다면, matrix[i][j] = 1 (유향 그래프의 경우) 또는 matrix[i][j] = matrix[j][i] = 1 (무향 그래프의 경우)로 설정합니다. 인접 행렬의 장점은 간선의 존재 여부를 O(1) 시간 복잡도로 확인할 수 있다는 점입니다. 하지만, 많은 정점에 비해 연결된 간선이 적은 희소 그래프의 경우 메모리 낭비가 발생할 수 있습니다.

2. 인접 리스트(Adjacency List)

인접 리스트는 각 정점에 연결된 정점들의 리스트를 사용하여 그래프를 표현합니다. 각 정점마다 연결된 정점들의 정보를 저장하는 리스트를 갖고 있어, 메모리 사용이 덜하지만 특정 정점과 연결된 정점을 찾는 데는 O(V) (V는 정점의 수) 시간이 걸립니다. 작은 정점 개수의 그래프는 인접 행렬보다 인접 리스트가 더 유리합니다.

알고리즘 문제: 최단 경로 찾기

문제 설명

주어진 그래프의 노드와 간선 정보가 있을 때, 특정 시작 노드에서 모든 다른 노드로 가는 최단 경로의 거리를 구하는 알고리즘을 구현하세요. 이 문제는 다익스트라(Dijkstra) 알고리즘을 사용하여 해결할 수 있습니다.

입력 형식

            - 첫 번째 줄: 정점의 수 V와 간선의 수 E
            - 두 번째 줄부터 E줄: 간선의 정보 u v w (정점 u에서 정점 v로 가는 가중치 w)
            - 마지막 줄: 시작 정점 S

예제 입력

예제 출력

풀이 과정

다익스트라 알고리즘은 우선순위 큐를 통해 현재까지 발견된 노드 중 최단 거리인 노드를 선택하고, 해당 노드와 인접한 노드의 거리를 갱신하는 방식으로 진행됩니다.

그래프를 인접 리스트 형태로 초기화합니다.
우선순위 큐를 사용하여 시작 정점으로부터의 거리를 초기화합니다.
우선순위 큐에서 거리가 가장 짧은 정점을 선택하고, 해당 정점과 연결된 모든 정점의 거리를 갱신합니다.
모든 정점이 확인될 때까지 2~3단계를 반복합니다.

C# 코드 구현


using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int V = int.Parse(input[0]); // 정점 수
        int E = int.Parse(input[1]); // 간선 수

        List> edges = new List>();
        for (int i = 0; i < E; i++)
        {
            var edgeInput = Console.ReadLine().Split();
            int u = int.Parse(edgeInput[0]) - 1; // 0-indexed
            int v = int.Parse(edgeInput[1]) - 1; // 0-indexed
            int w = int.Parse(edgeInput[2]);
            edges.Add(Tuple.Create(u, v, w));
        }
        
        int startVertex = int.Parse(Console.ReadLine()) - 1; // 0-indexed
        Dijkstra(V, edges, startVertex);
    }

    static void Dijkstra(int V, List> edges, int startVertex)
    {
        // 그래프 초기화
        List>> graph = Enumerable.Range(0, V)
                                                        .Select(x => new List>())
                                                        .ToList();

        foreach (var edge in edges)
        {
            graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
            graph[edge.Item2].Add(Tuple.Create(edge.Item1, edge.Item3)); // 무향 그래프
        }

        // 거리 배열 초기화
        int[] distances = new int[V];
        for (int i = 0; i < V; i++)
            distances[i] = int.MaxValue;
        distances[startVertex] = 0;

        // 우선순위 큐 초기화
        var priorityQueue = new SortedSet>();
        priorityQueue.Add(Tuple.Create(0, startVertex)); // (거리, 정점)

        while (priorityQueue.Any())
        {
            var current = priorityQueue.Min;
            priorityQueue.Remove(current);
            int currentDistance = current.Item1;
            int currentVertex = current.Item2;

            // 이미 더 짧은 경로가 발견된 경우 스킵
            if (currentDistance > distances[currentVertex])
                continue;

            foreach (var neighbor in graph[currentVertex])
            {
                int neighborVertex = neighbor.Item1;
                int edgeWeight = neighbor.Item2;

                // 거리 갱신
                if (distances[currentVertex] + edgeWeight < distances[neighborVertex])
                {
                    distances[neighborVertex] = distances[currentVertex] + edgeWeight;
                    priorityQueue.Add(Tuple.Create(distances[neighborVertex], neighborVertex));
                }
            }
        }

        // 결과 출력
        for (int i = 0; i < V; i++)
        {
            if (distances[i] == int.MaxValue)
                Console.WriteLine("INF");
            else
                Console.WriteLine(distances[i]);
        }
    }
}

결론

이번 강좌를 통해 그래프에 대한 기본적인 개념과 표현 방법, 그리고 C#으로 다익스트라 알고리즘을 구현하여 최단 경로 문제를 해결하는 방법을 배웠습니다. 알고리즘 문제는 지속적인 연습이 필요합니다. 다양한 문제를 풀어보며 자신만의 해결 방법을 찾아보시길 바랍니다.

서론