컴공 전공이든 복수전공이든 부전공이든 모두들 그래프 자료구조에 대해서 들어봤을 것이다. 그리고 뭘 뜻하는지도 알고 있을 것이다. 나도 그랬다. 나는 내가 그래프 이론을 충분히 이해하고 있고 DFS, BFS, 최단경로 문제등이 나오면 정말 쉽게 풀 수 있을 줄 알았다. 그러나 막상 문제를 마주하고 구현을 해보려니까 뭐 기억도 잘 안나고 어떻게 응용할지도 감이 안오더라. 그래서 공부를 하고, 예제를 풀어본 뒤 정리해서 글을 올린다.
그래프 자료구조
DFS, BFS는 그래프를 순회하는 알고리즘이다. 따라서 그래프 자료구조부터 알 필요가 있다.
그래프란, 수학시간에 봤던 X축있고 Y축있는 그래프도 있지만, 여기서 말하는 그래프는 정점(vertex or node)과 간선(edge or link)로 이루어진 자료구조이다. 그 생김새는 아래와 같다.
위의 사진을 보면, 그래프의 종류와 생김새를 알 수 있다. 그래프 중의 구성 요소인 정점과 간선 중에서, 간선은 방향성과 가중치가 있을 수 있다. A 정점과 D정점 사이에 A -> D 이런식으로 화살표가 있을 경우, A정점에서 D정점으로 갈 수 있지만, D정점에서 A정점으로 갈 수는 없다. 그리고, 간선 위에 숫자가 있을 경우, 이를 가중치라 하고, 거리, 시간, 비용 등의 개념으로 사용된다. 각 간선이 한 도시에서 다른 도시로 가는 시간이라 했을 때, A정점에서 D정점으로 가는데는 1시간, A정점에서 C정점으로 가는데는 2시간이 걸린다는 뜻이다.
이러한 그래프를 컴퓨터상에서 처리하기 위해서, 우리는 인접행렬과 인접리스트라는 방식으로 그래프를 표현한다.
인접 행렬은 노드의 갯수가 N이라 할 때, N * N 행렬을 만들고, i번째 노드와 j번째 노드 사이에 간선이 있다면 1, 그 간선에 가중치가 있다면 그 가중치만큼을 matrix[i][j]에 표현한다. 만약 어느 그래프가 방향성이 없고 가중치가 없다면, 그 그래프는 모든 원소가 0 또는 1이고, 대각선을 기준으로 대칭인 행렬이 된다. 방향성이 있다면, 그 행렬은 대칭이 아닐 수 있다. 가중치가 있다면, 행렬의 원소의 값은 0 또는 1이 아닐 수 있다.
인접행렬로 나타낼 경우, 많은 특징이 있겠지만 가장 큰 특징은 메모리를 비효율적으로 쓰게 된다. 정점이 10000개인데 간선이 1개밖에 없는 그래프를 생각해보자. 그 그래프의 인접행렬은 10000 * 10000의 크기를 갖지만, 딱 1개의 원소만 1이고 나머지는 전부 0이다. 그러므로 비효율적인 표현방법이다.
인접 리스트는 이와는 달리, 연결되어있는 점을 연결리스트의 형태로 표현한 것이다. 그 생김새는 아래와 같다.
가중치가 있을 경우, 연결된 노드와 가중치를 묶어서 저장함으로써 정점간의 링크의 가중치를 표현한다.
정리하자면
- 그래프는 정점의 집합과 간선의 집합으로 이루어진다.
- 인접행렬, 인접 리스트 2가지 방법으로 표현한다.
- 유향 그래프, 무향 그래프 등 방향성 존재 여부로 나뉜다.
- 간선에 가중치가 있다면, 인접행렬에 1이 아닌 다른 값이 있을 수 있다.
클래스와 메소드를 다 구현할 건 아니고, 이러한 특징을 가진 자료구조라는 것만 알아보고 마치겠다. 다음에는
- 그래프 순회 - BFS
- 그래프 순회 - DFS
- 위상 정렬(Topological Sorting)
- 최소 신장 트리 - Kruskal
- 최소 신장 트리 - Prim
- 최단 경로 알고리즘 - 다익스트라
- 최단 경로 알고리즘 - 플로이드
위의 알고리즘들에 대해서 알아보도록 하겠다.
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘 자습]그래프(Graph) - 2. DFS(깊이 우선 탐색)의 정의와 활용, 예제, 파이썬(Python3) (1) | 2020.03.04 |
|---|---|
| [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) (1) | 2020.03.04 |
| [프로그래머스 탐욕법]저울 - Python3 (0) | 2020.02.28 |
| [프로그래머스 연습]124나라의 숫자 - Python3 (0) | 2020.02.27 |
| [프로그래머스 연습]2 X N 타일링 - Python3 (0) | 2020.02.27 |
