Unity 개발자를 위한 Graph(그래프)의 이해

그래프(Graph)는 노드(Node)와 간선(Edge)으로 이루어진 자료구조입니다. 노드들은 서로 자유롭게 연결될 수 있으며, 트리(Tree) 보다 훨씬 일반적인 형태의 구조라고 볼 수 있습니다. 트리는 “사이클이 없고 루트가 있는 계층 구조”에 해당하는 특수한 그래프입니다.

이 문서에서는 그래프의 기본 개념과 용어를 정리하고, 트리와의 차이, 대표적인 표현 방식(인접 리스트, 인접 행렬), 그리고 게임/Unity에서 그래프 개념이 어떻게 쓰이는지를 그림과 함께 살펴보겠습니다. 실제 코드 구현보다는 개념 이해에 초점을 맞춘 이론 중심 문서입니다.

1. 그래프의 기본 개념

그래프는 다음 두 가지 요소로 구성됩니다.

정점(노드, Vertex / Node): 점 하나를 의미합니다. 게임에서 특정 위치, 도시 하나, 유저 한 명 등을 표현할 수 있습니다.
간선(Edge): 두 정점을 연결하는 선입니다. 이동 가능한 경로, 친구 관계, 통신 연결 등을 표현할 수 있습니다.

아주 단순한 그래프 예시는 다음과 같습니다.

정점 집합(V): { A, B, C, D }
간선 집합(E): { (A, B), (A, C), (B, D), (C, D) }

그림으로 표현하면:

    A
   / \
  B   C
   \ /
    D

그래프에는 몇 가지 변형 개념이 더 있습니다.

방향 그래프(Directed Graph)
간선에 방향이 있는 그래프 (A → B)
무방향 그래프(Undirected Graph)
간선에 방향이 없는 그래프 (A — B)
가중치 그래프(Weighted Graph)
간선에 비용/거리/시간 등의 값이 있고, 최단 경로 문제에서 자주 사용
ex) (A —3→ B) : A에서 B까지 이동 비용이 3
사이클(Cycle)
A → B → C → A처럼 다시 시작점으로 돌아오는 경로가 존재할 때
연결 그래프(Connected Graph)
그래프 내의 모든 정점이 서로 도달 가능한 그래프
비연결 그래프(Disconnected Graph)
그래프가 독립된 여러 개의 연결 그룹(Connected Components)으로 나뉘어 있는 형태
게임 맵 구역이 서로 열려 있지 않은 경우처럼 따로 노는 그래프 조각들이 존재

간단한 방향 그래프와 가중치 그래프 예시는 다음과 같습니다.

1) 방향 그래프 예시

A → B → C
│       ↑
└──→ D ─┘

2) 가중치 그래프 예시 (간선에 비용 표시)

     (A)
    /   \
  2/     \5
  /       \
(B)---3---(C)

위 그래프에서:
A → B 비용 = 2
A → C 비용 = 5
B → C 비용 = 3

2. 그래프와 트리의 관계

트리는 그래프의 특수한 형태입니다. 그래서 트리를 설명할 때 “사이클이 없는 연결 그래프”라고 표현하기도 합니다. 그러나 트리와 그래프를 혼동하지 않으려면 차이를 명확히 알고 있어야 합니다.

트리와 그래프를 한눈에 비교하면 다음과 같습니다.

트리(Tree): 사이클이 없고, 루트가 있으며, 부모–자식 구조가 명확한 그래프
그래프(Graph): 노드와 간선의 일반적인 구조. 방향/무방향, 사이클 여부 모두 가능

예를 들어 아래 두 그림을 비교해 보면 감이 더 잘 잡힙니다.

1) 트리 예시 (사이클 없음, 루트 존재)

        A (Root)
       / \
      B   C
     / \
    D   E

- 부모/자식 관계가 명확
- A에서 시작해 아래로만 내려가는 계층 구조
- 사이클이 없음


2) 일반 그래프 예시 (사이클 존재, 루트 개념 없음)

    A ---- B
    |      |
    |      |
    C ---- D

- A, B, C, D 모두 동등한 노드
- 부모/자식이라는 개념이 없음
- A → B → D → C → A처럼 사이클이 존재

정리하면, 트리는 그래프 중에서 “사이클이 없고, 하나의 루트에서 전체가 연결된 구조”만 따로 부르는 이름입니다. 트리를 이해하고 나면, 트리가 그래프의 일종이라는 사실도 자연스럽게 받아들일 수 있습니다.

3. 그래프의 표현 방식 (인접 리스트 / 인접 행렬)

그래프를 실제 코드나 메모리에서 표현하는 방법은 여러 가지가 있습니다. 가장 대표적인 두 가지는 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)입니다. 이 문서에서는 개념만 다루며, 구현 코드는 생략합니다.

3.1 인접 리스트(Adjacency List)

각 정점마다 “연결된 이웃 정점 목록”을 리스트로 들고 있는 표현 방식입니다. 정점 수에 비해 간선 수가 많지 않은 경우(희소 그래프)에 메모리를 효율적으로 사용합니다.

예시 그래프:

    A
   / \
  B   C
   \ /
    D

인접 리스트 표현:

A: B, C
B: A, D
C: A, D
D: B, C

장점: 연결된 이웃만 저장하기 때문에 메모리 효율이 좋음. 대부분의 실전 그래프에서 선호.
단점: 특정 두 정점이 직접 연결되어 있는지 O(정점의 차수)만큼 순회해야 할 수 있음.

3.2 인접 행렬(Adjacency Matrix)

정점 수가 N개일 때, N x N 2차원 배열을 사용하여 “i에서 j로 가는 간선이 있는지”를 0/1 또는 가중치 값으로 기록하는 방법입니다.

예시 그래프 (정점: A, B, C, D)

    A
   / \
  B   C
   \ /
    D

정점 순서를 [A, B, C, D]라고 두면:

[인접 행렬] ------------------------

* 핵심 원칙
  행(Row) => 출발 노드
  열(Column) => 도착 노드

------------------------------------
* 무방향 그래프 (간선 있으면 1)

      A  B  C  D
    -------------
A |   0  1  1  0
B |   1  0  0  1
C |   1  0  0  1
D |   0  1  1  0

  -> 대칭 행렬

------------------------------------
* 아래처럼 방향이 있는 경우
  A -> B
  A -> C
  B -> D

      A  B  C  D
    ----------------
A |   0  1  1  0
B |   0  0  0  1
C |   0  0  0  0
D |   0  0  0  0

  -> 대칭 행렬 아님

장점: 두 정점 사이에 간선이 있는지 O(1) 시간에 바로 알 수 있음.
단점: 항상 N x N 크기의 배열이 필요하므로 정점 수가 많고 간선이 적으면 메모리 낭비가 심함.

정리하면, 그래프를 메모리에 어떻게 담을지 결정할 때는 정점 수, 간선 수, 그리고 자주 하는 연산(연결 여부 확인, 전체 순회 등)을 고려해야 합니다. 대부분의 알고리즘 예제나 실무 코드에서는 인접 리스트를 주로 사용합니다.

4. 그래프 탐색 개념 (DFS / BFS)

그래프 위에서 “어떤 노드들을 어떤 순서로 방문할 것인가”를 정하는 것이 그래프 탐색(Graph Traversal)입니다. 이때 가장 기초가 되는 두 가지 방식이 DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)입니다. 이 문서에서는 개념과 간단한 예시만 다룹니다.

아래와 같은 간단한 그래프를 예제로 사용합니다.

      A
     / \
    B   C
   / \   \
  D   E   F

각 정점의 연결 관계를 인접 리스트 형태로 적어 보면 다음과 같습니다(무방향 그래프 기준).

A: B, C
B: A, D, E
C: A, F
D: B
E: B
F: C

4.1 DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 말 그대로 “가능한 한 깊이 내려갔다가, 더 이상 내려갈 곳이 없으면 되돌아오는” 방식의 탐색입니다. 그래프 관점에서는 각 노드의 이웃(Neighbor)을 따라가며, 한쪽 방향으로 깊게 탐색한 뒤 막히면 이전 노드로 되돌아옵니다. 구현할 때는 재귀 호출 또는 스택(Stack)을 사용하는 것이 일반적입니다.

아래 설명은 “스택을 직접 사용하는 반복형 DFS” 관점으로, 각 단계에서 어떤 노드를 방문하고 스택 상태가 어떻게 변하는지를 함께 보여줍니다. 스택의 왼쪽이 바닥(bottom), 오른쪽이 top이라고 가정합니다.

준비) 스택에 A를 Push

Stack: A
Visited : -

----------------------------

Step 1) A Pop → 방문
A의 이웃 B, C를 스택에 Push (오른쪽 이웃을 먼저 Push하여 왼쪽 이웃이 먼저 Pop되도록 함)

Stack: C, B   (C, B 순으로 Push, B가 top)
Visited : A

----------------------------

Step 2) B Pop → 방문
B의 이웃 중 아직 방문하지 않은 D, E를 Push

Stack: C, E, D   (E를 먼저 Push, 그 다음 D → D가 top)
Visited : A, B

----------------------------

Step 3) D Pop → 방문
D의 이웃 B는 이미 방문했으므로 추가 Push 없음

Stack: C, E
Visited : A, B, D

----------------------------

Step 4) E Pop → 방문
E의 이웃 B는 이미 방문했으므로 추가 Push 없음

Stack: C
Visited : A, B, D, E

----------------------------

Step 5) C Pop → 방문
C의 이웃 중 아직 방문하지 않은 F를 Push

Stack: F
Visited : A, B, D, E, C

----------------------------

Step 6) F Pop → 방문
F의 이웃 C는 이미 방문했으므로 추가 Push 없음

Stack: (empty)
Visited : A, B, D, E, C, F

----------------------------

최종 DFS 방문 순서:
A → B → D → E → C → F

이처럼 DFS는 스택을 사용해 “한 방향으로 깊게 들어갔다가 막히면 되돌아오는” 패턴으로 이웃 노드들을 탐색합니다. 트리를 “사이클이 없는 그래프”라고 보면, DFS는 트리의 전위/후위 순회와 같은 계열의 탐색 방식으로 이해할 수 있습니다.

※ 동작을 시각적으로 확인해보기

아래 링크는 DFS(Depth-First Search)의 탐색 과정을 단계별로 시각화해 주는 도구입니다. 한 노드에서 시작해 가능한 한 깊이 내려갔다가, 더 이상 방문할 노드가 없으면 되돌아오며 탐색을 이어가는 흐름를 직접 확인할 수 있습니다. 재귀 호출이나 스택을 사용할 때 탐색 순서가 어떻게 형성되는지 이해하는 데 도움이 됩니다.

https://www.cs.usfca.edu/~galles/visualization/DFS.html

4.2 BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 시작 노드에서 가까운 순서대로 탐색을 확장해 나가는 방식입니다. 먼저 시작 지점에서 한 번에 도달할 수 있는 노드들을 모두 살펴보고, 그다음에는 두 번 이동해야 도달하는 노드들, 그 이후 단계의 노드들을 차례대로 방문합니다. 이러한 순서를 자연스럽게 만들기 위해 큐(Queue)를 사용합니다.

아래에서는 큐(Queue)의 왼쪽을 front(꺼내는 쪽), 오른쪽을 rear(넣는 쪽)이라고 가정합니다. 각 단계마다 큐 상태와 방문 순서를 함께 보면서 진행합니다.

준비) 큐에 A를 Enqueue

Queue: A
Visited: -

----------------------------

Step 1) A Dequeue → 방문
A의 이웃 B, C를 큐에 Enqueue

Queue: B, C
Visited: A

----------------------------

Step 2) B Dequeue → 방문
B의 이웃 중 아직 방문하지 않은 D, E를 Enqueue

Queue: C, D, E
Visited: A, B

----------------------------

Step 3) C Dequeue → 방문
C의 이웃 중 아직 방문하지 않은 F를 Enqueue

Queue: D, E, F
Visited: A, B, C

----------------------------

Step 4) D Dequeue → 방문
D의 이웃 B는 이미 방문했으므로 추가 없음

Queue: E, F
Visited: A, B, C, D

----------------------------

Step 5) E Dequeue → 방문
E의 이웃 B는 이미 방문했으므로 추가 없음

Queue: F
Visited: A, B, C, D, E

----------------------------

Step 6) F Dequeue → 방문
F의 이웃 C는 이미 방문했으므로 추가 없음

Queue: (empty)
Visited: A, B, C, D, E, F

----------------------------

최종 BFS 방문 순서:
A → B → C → D → E → F

이처럼 BFS는 큐를 이용해 “가까운 노드(같은 레벨)에 있는 정점들”부터 차례대로 방문합니다. 트리 관점에서 보면, 레벨 순회(Level-Order Traversal)와 동일한 패턴이며, 그래프에서 간선 수 기준 최단 거리를 찾을 때 기본적으로 사용되는 탐색 방법입니다.

※ 동작을 시각적으로 확인해보기

아래 링크는 BFS(Breadth-First Search)의 탐색 과정을 단계별로 시각화해 주는 도구입니다. 시작 노드에서 출발해 거리(레벨) 순서대로 탐색 범위가 넓어지는 과정을 확인할 수 있으며, 큐(Queue)에 노드가 어떻게 들어가고 빠지는지가 탐색 순서에 어떤 영향을 주는지도 직관적으로 볼 수 있습니다. DFS와 비교하면서 보면 두 탐색 방식의 차이가 더욱 분명해집니다.

https://www.cs.usfca.edu/~galles/visualization/BFS.html

정리하면, DFS와 BFS는 모두 그래프(또는 트리) 위에서 노드를 방문하는 기본적인 탐색 방법이며,

DFS: 깊이 위주 탐색, 스택(또는 재귀) 사용, 백트래킹/경로 탐색에 유리
BFS: 너비(레벨) 위주 탐색, 큐 사용, 최단 거리 탐색에 유리

트리를 “사이클이 없는 그래프”라고 보고 DFS/BFS를 적용하면, 전위/중위/후위/레벨 순회처럼 트리에서 이미 익숙한 개념들과 자연스럽게 연결해 이해할 수 있습니다.

5. 그래프가 활용되는 대표적인 사례 (게임/Unity 관점)

그래프를 직접 클래스로 구현하는 일은 많지 않지만, 게임 개발에서 그래프 개념은 여러 시스템의 설계와 이해에 직접적인 영향을 줍니다.

길찾기(Pathfinding) – 네비메쉬, 웨이포인트 그래프
맵을 여러 지점(노드)으로 나누고, 지점 사이의 연결(간선)을 사용하는 구조는 전형적인 그래프입니다. A* 알고리즘, 다익스트라 알고리즘 등은 모두 그래프 위에서 “최단 경로”를 찾는 알고리즘입니다.
맵/지역 간 이동 구조
필드1 ↔ 필드2 ↔ 던전1 ↔ 마을처럼, 게임 내 지역 간 이동 관계도 그래프로 표현할 수 있습니다. 어떤 지역이 막혀 있거나(간선 제거), 새로 개방되는지(간선 추가)에 따라 전체 맵 동선이 달라집니다.
퀘스트/컨텐츠 의존 관계
어떤 퀘스트를 완료해야 다음 퀘스트를 받을 수 있는 구조, 어떤 컨텐츠를 열어야 다른 컨텐츠가 해금되는 구조도 그래프로 볼 수 있습니다. 사이클이 없도록 설계하면 “DAG(유향 비순환 그래프)”가 됩니다.
소셜 그래프(친구/길드 관계)
유저 간 친구 관계, 길드 간 동맹/적대 관계도 그래프 구조입니다. 추천 친구 기능, 네트워크 분석, 특정 유저 그룹 찾기 등의 기능에서 그래프 이론이 사용될 수 있습니다.

정리하면, 실무에서는 그래프를 직접 구현하기보다는 개념적으로 이해하고 설계에 반영하는 경우가 많습니다. 어떤 시스템이 “노드 + 관계” 구조를 가진다면, 거의 대부분 그래프로 모델링할 수 있습니다.

마무리

그래프(Graph)는 노드와 간선으로 이루어진 일반적인 구조입니다. 방향/무방향, 가중치 유무, 사이클 존재 여부 등 다양한 변형이 있으며, 길찾기, 의존 관계, 소셜 네트워크 등 수많은 문제를 표현할 수 있는 강력한 모델입니다.

트리는 이 그래프들 중에서 사이클이 없고, 하나의 루트에서 전체가 연결된 구조만을 따로 부르는 이름입니다. 그래프를 먼저 이해해 두면, 트리(Tree), 이진 트리(Binary Tree), 이진 탐색 트리(BST), 힙(Heap) 등 이후 자료구조들이 그래프의 어떤 특수한 형태인지 훨씬 쉽게 받아들일 수 있습니다.

※ 다음 글에서는 Tree(트리) 구조를 살펴보며, 그래프의 한 형태로 볼 수 있는 트리가 사이클이 없는 계층적 구조로 어떻게 정리되는지를 중심으로 설명합니다.

저작자표시 비영리 동일조건 (새창열림)

'자료 구조' 카테고리의 다른 글

Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 (0)	2025.12.11
Unity 개발자를 위한 C# Tree(트리) 구현 (0)	2025.12.10
Unity 개발자를 위한 C# PriorityQueue(우선순위 큐) 구현 (0)	2025.12.10
Unity 개발자를 위한 C# Dictionary(딕셔너리) 구현 (0)	2025.12.08
Unity 개발자를 위한 C# HashSet(해시셋) 구현 (0)	2025.12.07

대박 게임 개발 연구소

Unity 개발자를 위한 Graph(그래프)의 이해

1. 그래프의 기본 개념

2. 그래프와 트리의 관계

3. 그래프의 표현 방식 (인접 리스트 / 인접 행렬)

3.1 인접 리스트(Adjacency List)

3.2 인접 행렬(Adjacency Matrix)

4. 그래프 탐색 개념 (DFS / BFS)

5. 그래프가 활용되는 대표적인 사례 (게임/Unity 관점)

마무리

'자료 구조' 카테고리의 다른 글

티스토리툴바

Unity 개발자를 위한 Graph(그래프)의 이해

1. 그래프의 기본 개념

2. 그래프와 트리의 관계

3. 그래프의 표현 방식 (인접 리스트 / 인접 행렬)

3.1 인접 리스트(Adjacency List)

3.2 인접 행렬(Adjacency Matrix)

4. 그래프 탐색 개념 (DFS / BFS)

5. 그래프가 활용되는 대표적인 사례 (게임/Unity 관점)

마무리

'자료 구조' 카테고리의 다른 글

관련글

티스토리툴바