그래프의 개념을 이해하고 이를 실제 코드로 구현할 수 있습니다. 구현 그래프를 탐색하고 최단 경로를 구할 수 있습니다.
1편은 그래프의 개념입니다.
총 3편으로 준비했습니다.
1. 그래프의 개념
2. 그래프의 탐색
3. 그래프 몸풀기 문제
그래프는 노드(Vertex)과 간선(Edge)을 이용한 비선형 데이터 구조입니다. 보통 그래프는 데이터 간의 관계를 표현하는 데 사용합니다. 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현합니다. 간선은 방향이 있을 수도 있고 없을 수도 있습니다. 만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현합니다. 노드, 간선, 가중치라는 용어를 예와 함께 알아봅시다.
그래프 용어 정리
예를 들어 도시 간의 인구 이동을 그래프로 표현하면 다음과 같습니다.
그림에서 동그라미로 표현한 것이 노드, 화살표로 표현한 것이 간선, 간선 위에 숫자로 표현한 것이 가중치입니다. 노드에는 어떤 데이터가 들어 있습니다. 그리고 노드 사이에 있는 것이 간선입니다. 인구 이동의 경우 어디서 얼마나 이동했는지 표시할 필요가 있으므로 간선에 가중치를 표현했습니다.
그래프의 특징과 종류
그래프는 방향성, 가중치, 순환 특성에 따라 종류를 구분할 수 있습니다.
흐름을 표현하는 방향성
간선은 방향을 가질 수도 있고 없을 수도 있습니다. 방향이 있는 간선을 포함하면 방향 그래프(Directed Graph), 방향이 없는 간선을 포함하면 무방향 그래프(Undirected Graph)라고 합니다.
이때 방향 그래프는 어느 한쪽으로만 간선이 있는 것이 아니라 서로 반대를 가리키는 간선이 있을 수도 있습니다.
흐름의 정도를 표현하는 가중치
두 번째 특성은 가중치입니다. 어떤 데이터는 흐름의 방향뿐 아니라 양도 중요할 수 있습니다. 그런 정도를 간선에 표현할 때 이를 가중치라고 합니다. 가중치가 있는 그래프를 가중치 그래프(Weight Graph)라고 합니다.
시작과 끝의 연결 여부를 보는 순환
마지막 특성은 순환입니다. 순환은 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것을 말합니다. 순환이 존재하는 그래프를 순환 그래프(Cycle Graph)라 하고, 순환이 존재하지 않는 그래프를 비순환 그래프(Acyclic Graph)라고 합니다.
앞서 언급했듯이 특정 노드에서 시작해 간선을 따라 다시 돌아오면 순환 그래프입니다. 다음의 경우 2 → 4 → 3 → 2이므로 그래프의 일부분이 순환합니다. 1, 2, 3은 모두 연결되어 있긴 하지만 순환하진 않습니다.
또, 그래프는 간선의 방향 유무에 따라 방향 그래프와 비방향 그래프로 나눌 수 있습니다.
그래프 구현
예를 들어 서울에서 부산으로 유동 인구가 8,000명 발생했다와 같은 내용을 그래프로 표현한다고 해봅시다. 그러면 그래프의 노드, 간선, 방향, 가중치와 문장의 의미를 이렇게 연결하여 정리해볼 수 있습니다.
- 데이터를 담고 있는 노드(서울, 부산)
- 노드를 잇는 간선(서울과 부산의 연결 유무)
- 간선의 방향(서울에서 부산 방향으로)
- 간선의 가중치(유동 인구 8,000명)
그래프의 구현 방식에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있습니다. 두 방법으로 구현해봅시다.
인접 행렬 그래프 표현
인접 행렬은 배열을 활용하여 구현하는 경우가 많습니다. 이때 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고, 인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 그래프를 표현할 수 있습니다. 다음은 서울에서 부산으로 향하는 간선이 있는 그래프입니다.
이것을 인접 행렬로 표현하면 다음과 같습니다. 인접 행렬의 세로 방향 인덱스를 출발, 가로 방향 인덱스를 도착으로 하니 서울(0) → 부산(1)으로 향하는 가중치가 400(km)인 그래프가 표현되었습니다. 그리고 -로 표현한 가중치는 실제 코드에서는 굉장히 큰 값을 넣거나 -1로 정합니다.
인접 리스트 그래프 표현
인접 리스트로 그래프를 표현하려면 우선 다음과 같이 적절한 노드를 정의해야 합니다. 그림에서 보듯 값(v), 가중치(w), 다음 노드(next)를 묶어 관리합니다.
인접 리스트 그래프 표현 방식은 다음과 같은 과정으로 동작합니다.
- 우선은 노드 개수만큼 배열을 준비합니다.
- 배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결합니다.
이제 동작하는 과정을 자세히 살펴보겠습니다.
01단계 우선은 노드 개수만큼 배열을 준비합니다.
02단계 이 상태에서 1 → 2(가중치 3)을 표현해보겠습니다.
03단계 이어서 2 → 1(가중치 6)을 표현해보겠습니다.
04단계 정의한 노드의 다음 노드가 연결되는 모습도 살펴봅시다. 2 → 3(가중치 5)을 표현해볼까요? 이미 배열에는 노드 2가 연결되어 있습니다. 다음 노드가 NULL인 노드를 찾아 2 → 3(가중치5)을 표현한 노드를 연결합니다.
05단계 위와 같은 방식으로 그래프를 연결하면 다음과 같이 인접 리스트를 완성할 수 있습니다. 눈으로만 보고 넘어가지 말고 반드시 손으로 그려가며 꼭 그래프 전체를 표현해보기 바랍니다.
인접 행렬과 인접 리스트의 장단점
두 방식으로 그래프를 표현할 때 어느 한쪽이 매우 뛰어나거나 하지 않습니다. 모두 장단점이 있습니다.
인접 행렬의 장단점
인접 행렬은 크게 두 가지 단점이 있습니다. 첫 번째 단점은 인접 행렬로 희소 그래프를 표현하는 경우입니다. 희소 그래프란 노드 수에 비해 간선 수가 매우 적은 그래프를 말합니다. 인접 행렬은 크기가 고정되어 있으므로 최악의 경우를 고려해서 크기를 결정해야 합니다. 따라서 노드가 N개 있을 때 모든 간선이 연결되는 최악의 경우를 고려해서 N × N 크기의 인접 행렬이 필요합니다. 이럴 때 간선 수가 적으면 이렇게 확보한 N × N 크기의 인접 행렬 공간 중 대부분의 공간은 실제로 사용하지 않으므로 비효율적입니다. 두 번째 단점은 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우입니다. 예를 들어 노드값이 순차적으로 증가하지 않고 1, 2, 3, 999와 같이 간격이 크면 가장 큰 노드의 값인 999를 기준으로 인접 행렬의 크기를 잡아야 합니다.
인접 행렬의 장점은 간선의 정보를 확인할 때의 시간 복잡도가 O(1)로 좋습니다. 인접 행렬에서는 인덱스 임의 접근으로 노드 간 간선 정보를 바로 확인할 수 있기 때문입니다. 예를 들어 2에서 93이 연결되어 있는지 탐색하려면 array[2][93]에 가중치가 있는지만 확인하면 됩니다. 구현 난이도가 낮다는 것도 인접 행렬의 장점입니다.
인접 리스트의 장단점
인접 리스트는 인접 행렬과 정반대의 장단점을 가집니다. 인접 리스트는 실제 연결된 노드에 대해서만 노드의 값을 노드에 담아 연결하기만 하면 됩니다. 물론 최악의 경우 각 노드에서 모든 노드에 간선이 연결되어 있을 때는 효율이 떨어질 수 있습니다만 그런 경우는 굉장히 드뭅니다. 보통은 인접 리스트를 활용하면 메모리를 아낄 수 있다고 이야기합니다. 간선 정보를 확인할 때는 특정 노드에서 시작하여 연결된 노드 개수가 많으면 많을수록 노드를 연결한 리스트의 길이만큼 탐색해야하므로 탐색 시간이 O(N)입니다.
표로 정리한 인접 행렬과 인접 리스트의 장단점은 다음과 같습니다.
그래프 문제를 풀 때는 인접 행렬과 인접 리스트 방식 중 더 좋은 것을 선택해야 하지만 보통은 시간 제약에서 장점을 취하기 위해 인접 행렬 방식으로 그래프 문제를 푸는 경우가 많습니다. 문제에서 노드 개수가 1,000개 미만으로 주어지는 경우에는 인접 행렬을 사용하면 됩니다.
※ 노드의 데이터가 숫자가 아니라 문자열이면 문자열을 숫자로 매핑하여 인접 행렬의 인덱스로 사용하면 됩니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
