그래프와 그래프 탐색 (Graph & Graph Search) 정리

공재원
∙∙조회 4

1. 그래프란?

그래프(Graph)는 정점(Vertex)과 정점 사이를 연결하는 간선(Edge)으로 구성된 자료구조이다.

기본 구성 요소

  • Vertex (정점): 데이터를 표현하는 개체이다. 도시, 사람, 웹페이지, 게임의 타일 등이 해당한다.
  • Edge (간선): 정점과 정점 사이의 관계를 나타내는 연결이다. 도로, 친구 관계, 웹페이지 링크, 인접 타일 등이 해당한다.

그래프의 분류

기준종류설명
방향성방향 그래프간선에 방향이 존재한다.
방향성무방향 그래프간선에 방향이 없다.
가중치가중 그래프간선이나 이동 관계에 비용이 존재한다.
가중치비가중 그래프간선의 비용을 별도로 구분하지 않는다.
연결성연결 그래프모든 정점이 서로 경로로 연결되어 있다.
연결성비연결 그래프서로 도달할 수 없는 정점이 존재한다.
순환성순환 그래프시작 정점으로 돌아오는 경로가 존재한다.
순환성비순환 그래프순환 경로가 존재하지 않는다.

비순환 방향 그래프는 DAG(Directed Acyclic Graph)라고 한다.

이 프로젝트에서는 무방향·가중·격자(Grid) 기반 그래프를 다룬다.

2. 그래프의 표현 방식

그래프는 정점과 간선의 연결 관계를 저장하는 방법에 따라 여러 방식으로 표현할 수 있다.

인접 리스트 (Adjacency List)

각 정점이 자신과 연결된 다른 정점의 목록을 가지는 방식이다.

예를 들어 A와 B, C가 연결되어 있다면 A의 인접 리스트에는 B와 C가 저장된다.

특징

  • 메모리 복잡도: O(V + E)
  • 특정 정점의 이웃 탐색: O(deg(v))
  • 간선이 적은 희소 그래프에서 효율적이다.
  • 실제로 연결된 정점만 저장하므로 메모리를 절약할 수 있다.

V는 정점의 수, E는 간선의 수, deg(v)는 특정 정점에 연결된 간선의 수이다.

이 프로젝트에서는 List<GraphNode> adjacents를 사용하여 인접 리스트를 구현한다.

인접 행렬 (Adjacency Matrix)

정점의 수를 기준으로 V × V 크기의 행렬을 만들어 연결 관계를 저장하는 방식이다.

두 정점 사이에 간선이 존재하는지 행렬의 값을 통해 확인한다.

특징

  • 메모리 복잡도: O(V²)
  • 두 정점 사이의 연결 여부 확인: O(1)
  • 간선이 많은 밀집 그래프에서 활용하기 좋다.
  • 연결이 없는 정점 사이의 공간도 사용한다.

두 방식 비교

구분인접 리스트인접 행렬
저장 방식연결된 정점 목록2차원 행렬
메모리O(V + E)O(V²)
간선 확인목록 탐색 필요O(1)
이웃 탐색연결된 정점만 순회모든 정점 확인
적합한 그래프희소 그래프밀집 그래프

3. 격자 그래프 (Grid Graph)

격자 그래프는 2차원 격자의 각 칸을 정점으로 취급하고, 서로 인접한 칸을 간선으로 연결한 그래프이다.

게임의 미로, 타일맵, 길찾기 시스템 등에서 활용할 수 있다.

격자와 정점의 연결

일반적인 2차원 격자에서는 각 칸이 상하좌우에 있는 칸과 연결된다.

  • 위쪽 칸
  • 아래쪽 칸
  • 왼쪽 칸
  • 오른쪽 칸

이러한 연결 관계를 그래프로 표현하면 탐색 알고리즘을 적용할 수 있다.

2차원 좌표와 1차원 인덱스 변환

2차원 격자를 1차원 배열로 저장할 때는 행 우선(Row-major) 방식으로 변환할 수 있다.

2차원 좌표 → 1차원 인덱스

id = r * cols + c

  • r: 행(Row)
  • c: 열(Column)
  • cols: 전체 열의 개수
  • id: 1차원 배열의 인덱스

행이 하나 증가하면 인덱스가 cols만큼 증가하고, 열이 하나 증가하면 인덱스가 1만큼 증가한다.

1차원 인덱스 → 2차원 좌표

  • r = id / cols
  • c = id % cols

정수 나눗셈과 나머지 연산을 이용하여 원래의 행과 열을 구한다.

이 프로젝트에서는 Graph.Init(int[,] grid)와 Heuristic 메서드에서 이러한 좌표 변환을 활용한다.

장애물 표현

격자에서 이동할 수 없는 칸은 특정 값으로 구분할 수 있다.

이 프로젝트에서는 grid[r, c] == -1을 장애물로 처리한다.

장애물도 노드 객체로 생성하지만 다른 노드와의 인접 연결은 만들지 않는다.

GraphNode.CanVisit은 다음 두 조건을 모두 만족해야 true를 반환한다.

  • weight >= 0: 장애물이 아니어야 한다.
  • adjacents.Count > 0: 연결된 인접 노드가 있어야 한다.

이를 통해 장애물과 고립된 노드를 탐색 대상에서 제외한다.

깊이 우선 탐색(DFS)은 시작 정점에서 가능한 한 깊은 곳까지 이동한 뒤 더 이상 진행할 수 없으면 이전 정점으로 돌아오는 탐색 방식이다.

사용하는 자료구조

Stack (스택)을 사용한다.

스택은 LIFO 구조이므로 가장 마지막에 추가된 정점을 먼저 처리한다.

동작 과정

  1. 시작 정점을 스택에 추가한다.
  2. 스택에서 정점을 하나 꺼낸다.
  3. 아직 방문하지 않은 인접 정점을 확인한다.
  4. 방문할 정점을 스택에 추가한다.
  5. 스택이 빌 때까지 반복한다.

방문한 정점을 기록해야 같은 정점을 반복해서 방문하는 상황을 방지할 수 있다.

특징

  • 깊이 방향으로 먼저 탐색한다.
  • 스택을 이용하여 구현할 수 있다.
  • 재귀 호출을 이용해서도 구현할 수 있다.
  • 탐색 순서는 인접 정점의 방문 순서에 따라 달라진다.

시간 복잡도

O(V + E)

모든 정점과 간선을 확인하기 때문이다.

활용 사례

  • 연결 요소 탐색
  • 사이클 탐지
  • 위상 정렬
  • 트리의 깊이 기반 탐색

DFS는 깊이부터 탐색하므로 일반적인 비가중 그래프의 최단 경로를 찾는 용도로는 적합하지 않다.

너비 우선 탐색(BFS)은 시작 정점과 가까운 정점부터 차례대로 탐색하는 방식이다.

깊이 방향으로 내려가는 DFS와 달리 같은 깊이에 있는 정점을 먼저 확인한다.

사용하는 자료구조

Queue (큐)를 사용한다.

큐는 FIFO 구조이므로 먼저 추가된 정점을 먼저 처리한다.

동작 과정

  1. 시작 정점을 큐에 추가한다.
  2. 큐에서 정점을 하나 꺼낸다.
  3. 아직 방문하지 않은 인접 정점을 확인한다.
  4. 방문할 정점을 큐에 추가한다.
  5. 큐가 빌 때까지 반복한다.

방문 여부를 기록하여 이미 확인한 정점이 다시 큐에 추가되지 않도록 한다.

특징

  • 시작 정점과 가까운 정점부터 탐색한다.
  • 큐를 이용하여 구현한다.
  • 같은 깊이의 정점을 먼저 처리한다.
  • 비가중 그래프에서 최단 경로를 찾을 수 있다.

시간 복잡도

O(V + E)

모든 정점과 간선을 확인하기 때문이다.

활용 사례

  • 미로 탐색
  • 최단 단계 수 계산
  • 연결된 영역 탐색
  • 상태 공간 탐색

BFS와 최단 경로

BFS는 모든 간선의 비용이 동일한 비가중 그래프에서 최단 경로를 보장한다.

시작 정점에서 가까운 순서대로 탐색하므로 목적지에 처음 도달했을 때의 경로가 가장 적은 간선 수를 가진 경로이다.

가중치가 서로 다른 그래프에서는 BFS만으로 최저 비용 경로를 보장할 수 없다.

6. DFS와 BFS 비교

구분DFSBFS
탐색 방식깊이 우선너비 우선
자료구조StackQueue
탐색 순서깊은 정점부터가까운 정점부터
최단 경로일반적으로 보장하지 않음비가중 그래프에서 보장
시간 복잡도O(V + E)O(V + E)

두 알고리즘 모두 그래프 전체를 탐색할 수 있지만 탐색 순서와 적합한 문제에 차이가 있다.

7. 최단 경로 복원

BFS로 목적지에 도달하면 시작점에서 목적지까지 필요한 단계 수를 알 수 있다.

하지만 목적지까지 실제로 어떤 정점들을 거쳐 왔는지 확인하려면 이전 정점 정보를 기록해야 한다.

Previous

각 노드에 previous라는 이전 노드 참조를 저장한다.

현재 노드에서 새로운 인접 노드로 이동할 때 해당 인접 노드의 이전 노드를 현재 노드로 지정한다.

adjacent.previous = currentNode;

경로 복원 과정

  1. 목적지 노드에서 시작한다.
  2. 현재 노드의 previous를 확인한다.
  3. 이전 노드로 이동하면서 경로를 저장한다.
  4. 시작 노드에 도달할 때까지 반복한다.
  5. 저장된 경로를 뒤집는다.

목적지에서 시작점 방향으로 거슬러 올라가기 때문에 처음 저장된 경로는 역순이다.

따라서 마지막에 Reverse를 수행하여 시작점에서 목적지 방향으로 변경한다.

주의사항

  • 시작 노드의 previous는 null이어야 한다.
  • 탐색을 새로 시작하기 전에 이전 경로 정보가 남아 있지 않도록 초기화해야 한다.
  • 목적지에 도달할 수 없는 경우에는 경로를 복원하지 않아야 한다.

8. 시간 복잡도 정리

알고리즘자료구조시간 복잡도
DFSStackO(V + E)
BFSQueueO(V + E)
BFS 경로 복원Queue + PreviousO(V + E)

V는 정점의 수이고 E는 간선의 수이다.

인접 리스트를 사용하면 각 정점과 연결된 간선을 순회하는 방식으로 그래프를 탐색할 수 있다.

9. 프로젝트의 실제 구현 구조

GraphNode

그래프의 정점 하나를 표현하는 클래스이다.

  • id: 정점의 고유 번호이다.
  • weight: 해당 노드의 이동 비용 또는 가중치 정보를 저장한다.
  • adjacents: 현재 노드와 연결된 인접 노드 목록이다.
  • previous: 경로 복원에 사용할 이전 노드이다.
  • CanVisit: 탐색 가능한 노드인지 확인하는 프로퍼티이다.

Graph

전체 그래프의 구조를 관리하는 클래스이다.

  • rows: 격자의 행 개수이다.
  • cols: 격자의 열 개수이다.
  • nodes: 그래프의 모든 노드를 저장하는 1차원 배열이다.
  • Init(int[,] grid): 2차원 격자 데이터를 그래프 구조로 초기화한다.
  • ResetNodePrevious(): 모든 노드의 이전 노드 정보를 초기화한다.

GraphSearch

그래프 탐색과 길찾기 기능을 담당하는 클래스이다.

  • graph: 탐색할 그래프이다.
  • path: 탐색 결과 또는 복원된 경로를 저장한다.
  • Init(Graph graph): 탐색할 그래프를 설정한다.
  • DFS(GraphNode node): 깊이 우선 탐색을 수행한다.
  • BFS(GraphNode node): 너비 우선 탐색을 수행한다.
  • DFSRecursive(GraphNode node): 재귀 호출을 이용한 깊이 우선 탐색을 수행한다.
  • PathFindingBFS(startNode, endNode): BFS를 이용하여 비가중 그래프의 경로를 찾는다.
  • Dijkstra(start, goal): 가중치가 있는 그래프에서 최저 비용 경로를 찾는다.
  • AStar(start, goal): 실제 이동 비용과 목적지까지의 예상 비용을 함께 고려하여 경로를 찾는다.

구현 시 핵심 사항

  • Graph.nodes는 GraphNode[]이며 2차원 격자를 1차원으로 펼쳐 저장한다.
  • GraphNode.adjacents는 인접 리스트를 구성한다.
  • GraphSearch.path는 탐색 결과를 저장하며 새로운 탐색을 시작할 때 기존 내용을 초기화해야 한다.
  • previous는 목적지에서 시작점까지 경로를 역추적하는 데 사용한다.
  • DFSRecursive는 외부에서 호출하는 공개 메서드와 실제 재귀 탐색을 수행하는 내부 헬퍼 메서드로 구성한다.

10. 전체 구조 정리

그래프는 정점과 간선으로 관계를 표현하는 자료구조이다.

  • Vertex: 그래프를 구성하는 정점이다.
  • Edge: 정점 사이의 연결 관계이다.
  • Adjacency List: 각 정점의 연결 정보를 목록으로 저장한다.
  • Grid Graph: 2차원 격자를 그래프로 표현한다.
  • DFS: 스택을 사용하여 깊이 방향으로 탐색한다.
  • BFS: 큐를 사용하여 가까운 정점부터 탐색한다.
  • Previous: 이전 노드를 저장하여 경로를 복원한다.
  • Dijkstra: 가중치가 있는 그래프에서 최저 비용 경로를 탐색한다.
  • A*: 이동 비용과 목적지까지의 예상 비용을 활용하여 경로를 탐색한다.

핵심은 그래프를 통해 개체 사이의 연결 관계를 표현하고, 탐색 알고리즘을 이용하여 원하는 정점이나 경로를 찾는 것이다.