코딩 테스트 대비: 그래프 이론 기초 이해 및 적용 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 그래프 이론에 대해 알아보겠습니다. 그래프는 객체 간의 관계를 나타내는 자료구조로, 여러 가지 형태의 문제에 적용할 수 있습니다.

 

그래프의 기초 개념
그래프는 노드(node)와 간선(edge)으로 구성됩니다. 노드는 객체를 나타내며, 간선은 객체 사이의 관계를 표현합니다. 그래프는 방향성이 있는 방향 그래프와 방향성이 없는 무방향 그래프로 나뉩니다. 또한 간선에 가중치를 부여할 수 있는 가중 그래프도 존재합니다.

 

그래프의 표현 방법
그래프는 인접 리스트(adjacency list)와 인접 행렬(adjacency matrix)로 표현할 수 있습니다. 인접 리스트는 각 노드에 연결된 노드를 리스트로 저장하는 방법이며, 인접 행렬은 각 노드 간의 연결 여부를 행렬로 저장하는 방법입니다.

먼저 인접 리스트를 이용한 그래프 표현을 살펴보겠습니다. 다음은 C#으로 작성한 인접 리스트 표현의 예시입니다.

 

public class Graph {
    private List<int>[] _adjacencyList;

    public Graph(int nodeCount) {
        _adjacencyList = new List<int>[nodeCount];
        for (int i = 0; i < nodeCount; i++) {
            _adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int node1, int node2) {
        _adjacencyList[node1].Add(node2);
        _adjacencyList[node2].Add(node1);
    }
}

 

이제 인접 행렬을 이용한 그래프 표현을 살펴보겠습니다. 다음은 C#으로 작성한 인접 행렬 표현의 예시입니다.

 

public class Graph {
    private bool[,] _adjacencyMatrix;

    public Graph(int nodeCount) {
        _adjacencyMatrix = new bool[nodeCount, nodeCount];
    }

    public void AddEdge(int node1, int node2) {
        _adjacencyMatrix[node1, node2] = true;
        _adjacencyMatrix[node2, node1] = true;
    }
}

 

이상으로 그래프 이론의 기초에 대해 간단히 알아보았습니다. 다음 포스팅에서는 그래프 탐색 알고리즘인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 대해 다루겠습니다. 감사합니다!