--- title: "타일맵도 스킬 트리도 결국 같은 모양이다" description: "점과 선으로 보면 길찾기, 스킬 선행 조건, 던전 방 연결이 한 문제가 됩니다. 그래프를 인접 행렬과 인접 리스트 중 무엇으로 저장할지, 격자는 왜 저장하지 않아도 되는지 봅니다." author: "유니얼" pubDate: 2026-09-15 category: "programming/algorithm/graph" tags: ["자료구조"] canonical: https://blog.unialgames.com/posts/algo-graph-representation/ --- 게임을 만들다 보면 이름만 다르고 모양이 같은 문제를 여러 번 만납니다. - 타일맵에서 적이 플레이어에게 가는 길을 찾는다 - 이 스킬을 찍을 수 있는지, 선행 스킬이 다 찍혀 있는지 확인한다 - 절차적으로 만든 던전에서 모든 방이 실제로 이어져 있는지 검사한다 셋 다 **점과 그 점들을 잇는 선**의 문제입니다. 여기에 붙은 이름이 그래프입니다. 문제를 그래프로 옮겨 놓으면 셋에 같은 코드를 씁니다. 옮기는 첫 단계가 저장하는 방법을 정하는 것입니다. ## 점과 선에 이름을 붙이면 점을 **정점**, 정점을 잇는 선을 **간선**이라고 부릅니다. 그래프는 이 둘의 묶음입니다.
A B C D E
정점 다섯 개와 간선 다섯 개. 여기서부터 저장 방법이 갈린다.
무엇을 정점으로 두고 무엇을 간선으로 둘지는 문제마다 다릅니다. | 문제 | 정점 | 간선 | | --- | --- | --- | | 타일맵 이동 | 칸 하나 | 옆 칸으로 갈 수 있다 | | 스킬 트리 | 스킬 하나 | 이 스킬이 저 스킬의 선행이다 | | 던전 연결 | 방 하나 | 두 방을 잇는 통로 | | 월드 맵 | 도시 하나 | 도시를 잇는 길 | 간선에는 성질이 둘 붙을 수 있습니다. - **방향.** A 에서 B 로는 가는데 B 에서 A 로는 못 가는 경우입니다. 선행 스킬, 한 방향 점프대, 낭떠러지가 그렇습니다. 양쪽이 같으면 방향 없는 간선으로 둡니다 - **가중치.** 지나는 데 드는 비용입니다. 늪은 3, 포장된 길은 1 처럼 칸마다 다르게 둘 수 있습니다. 비용이 전부 같으면 가중치가 없는 것으로 봅니다 이 둘을 어떻게 두느냐가 나중에 쓸 수 있는 알고리즘을 정합니다. 가중치가 없으면 단순히 넓게 퍼뜨리는 탐색으로 최단 거리가 나오고, 가중치가 있으면 다익스트라 계열이 필요합니다. ## 저장하는 방법은 둘이다 같은 그래프를 두 가지로 저장할 수 있습니다.
A B C D E A B C D E 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 칸 스물다섯 개 가운데 열 개만 1 이다
정점 수만큼의 정사각 표. 이어졌으면 1, 아니면 0.
A B C B A D C A D D B C E E D 칸 열 개. 이어진 것만 자리를 차지한다
정점마다 이웃 목록 하나. 이어진 것만 자리를 차지한다.
 **인접 행렬**은 정점 수 V 에 대해 V 곱하기 V 짜리 표를 만들고, 두 정점이 이어졌으면 그 칸에 1 을 적습니다. 가중치가 있으면 1 대신 비용을 적습니다. **인접 리스트**는 정점마다 배열이나 리스트를 하나씩 두고 이어진 이웃만 넣습니다. 간선 하나가 양방향이면 양쪽 목록에 한 번씩 들어갑니다. 정점 다섯에 간선 다섯인 위 그래프에서 행렬은 칸 스물다섯 개를 쓰고 리스트는 열 개를 씁니다. 정점이 늘면 이 차이가 벌어집니다. ## 정점이 늘면 무엇이 벌어지는가 행렬이 쓰는 칸은 간선이 몇 개든 항상 V 의 제곱입니다. 리스트가 쓰는 칸은 정점 하나에 평균 몇 개가 붙어 있느냐에 따라 정해집니다. 정점 하나에 붙은 이웃 수가 정점 수에 가까워질수록 둘이 만납니다. 모든 정점이 서로 다 이어진 그래프라면 행렬과 리스트가 쓰는 칸이 같아지고, 그때는 표 한 장이 더 단순합니다. 게임에서 다루는 그래프는 대부분 반대쪽입니다. 타일맵 한 칸은 이웃이 넷이고, 방 하나에 붙은 통로는 두셋입니다. ## 무엇을 얻고 무엇을 잃는가
장점
  • 두 정점이 이어졌는지 한 번에 안다. 칸 하나만 읽으면 끝입니다. 이웃을 뒤질 필요가 없습니다.
  • 간선을 넣고 빼기가 싸다. 칸 하나를 켜고 끄는 것이 전부입니다.
  • 메모리가 한 덩어리다. 배열 하나라 참조가 흩어지지 않습니다.
단점
  • 간선이 없어도 자리를 차지한다. 정점이 만 개면 간선이 하나도 없어도 칸 1억 개입니다.
  • 이웃을 훑는 데 정점 수만큼 걸린다. 이웃이 넷뿐이어도 한 줄을 전부 읽어 0 을 건너뛰어야 합니다.
장점
  • 간선 수에 비례한다. 없는 간선에는 한 칸도 안 씁니다.
  • 이웃만 정확히 훑는다. 탐색은 이웃을 도는 일이 전부라 이것이 그대로 속도가 됩니다.
단점
  • 두 정점이 이어졌는지 물으면 목록을 뒤져야 한다. 이웃 수만큼 걸립니다.
  • 메모리가 흩어진다. 목록이 정점마다 따로 있어서 캐시에 불리합니다.
 그래서 고르는 기준은 이렇게 정리됩니다. | 이런 그래프면 | 무엇을 쓰나 | | --- | --- | | 정점이 많고 이웃은 몇 개뿐이다 (타일맵, 던전, 스킬 트리) | 인접 리스트 | | 정점이 적고 거의 다 이어져 있다 (도시 열몇 개의 전체 노선) | 인접 행렬 | | "A 와 B 가 이어졌나" 를 자주 묻는다 | 인접 행렬 | | 이웃을 훑는 일이 대부분이다 | 인접 리스트 | 게임 코드에서 마주치는 그래프는 거의 첫 줄과 마지막 줄에 해당합니다. 기본값은 인접 리스트입니다. ## 코드로 보면 두 코드가 하는 일은 같습니다. 다른 것은 `Visit` 에 닿기까지 몇 칸을 읽었느냐입니다. 이웃이 넷인 정점에서 리스트는 네 칸을 읽고, 행렬은 정점 수만큼 읽어 나머지를 버립니다. 가중치가 있으면 `bool` 대신 비용을 담습니다. 리스트라면 `List<(int to, float cost)>` 처럼 이웃과 비용을 같이 넣고, 행렬이라면 `float[,]` 에 비용을 적되 이어지지 않은 칸을 `float.PositiveInfinity` 로 채웁니다. 0 으로 채우면 "비용 0 으로 이어진 간선" 과 구별이 안 됩니다. ## 격자는 저장하지 않아도 그래프다 타일맵을 그래프로 쓰겠다고 인접 리스트를 만들 필요는 없습니다. 100 곱하기 100 짜리 맵이면 정점이 만 개이고, 이걸 행렬로 잡으면 칸이 1억 개인데 실제로 이어진 간선은 이만 개 남짓입니다. 리스트로 잡아도 사만 칸을 따로 들고 있어야 합니다. 그런데 격자에는 규칙이 있습니다. `(x, y)` 의 이웃은 언제나 `(x, y-1)`, `(x, y+1)`, `(x-1, y)`, `(x+1, y)` 입니다. **이어져 있다는 사실이 좌표 안에 이미 들어 있습니다.** 그래서 간선을 저장하는 대신 필요할 때 계산합니다. 이렇게 저장하지 않고 규칙으로만 존재하는 그래프를 암묵 그래프라고 부릅니다.
now 이웃 4개. 표에 저장한 것이 아니라 좌표로 계산한 것이다
상하좌우만 이웃으로 친다.
now 이웃 8개. 표에 저장한 것이 아니라 좌표로 계산한 것이다
대각선까지 이웃으로 치면 간선이 두 배가 된다.
 코드는 방향 배열 하나면 됩니다. ```csharp static readonly int[] DX = { 0, 0, -1, 1 }; static readonly int[] DY = { -1, 1, 0, 0 }; IEnumerable<(int x, int y)> Neighbors(int x, int y) { for (int d = 0; d < DX.Length; d++) { int nx = x + DX[d]; int ny = y + DY[d]; if (nx < 0 || ny < 0 || nx >= Width || ny >= Height) continue; if (Blocked[nx, ny]) continue; yield return (nx, ny); } } ``` 맵 밖을 걸러내는 줄과 벽을 걸러내는 줄이 간선을 만드는 자리입니다. 벽을 부수면 간선이 생기고 문을 잠그면 간선이 사라지는데, 자료구조는 아무것도 안 고쳐도 됩니다. 대각선을 넣을 때는 두 가지를 같이 정해야 합니다. - **비용.** 대각선 한 칸은 가로 한 칸보다 깁니다. 가로세로를 1 로 두면 대각선은 1.414 쯤입니다. 전부 1 로 두면 대각선으로 도는 길이 더 싸 보여서 경로가 지그재그로 나옵니다 - **모서리 통과.** 벽 두 장이 직각으로 만난 안쪽 모서리를 대각선으로 스치고 지나가는 문제입니다. 양옆 두 칸이 모두 막혀 있으면 그 대각선은 이웃으로 치지 않는다는 규칙을 넣어 막습니다. 안 넣으면 캐릭터가 벽 모서리를 뚫고 지나갑니다 정점을 번호로 다뤄야 할 때는 `y * Width + x` 로 칸 하나를 정수 하나에 접습니다. 방문 표시나 비용 배열을 일차원 배열로 잡을 수 있어서 격자를 다루는 코드가 짧아집니다. ## 정리 점과 선으로 보이면 그래프이고, 그래프로 옮기면 서로 달라 보이던 문제에 같은 코드를 쓸 수 있습니다. 저장하는 방법은 둘입니다. **인접 행렬**은 정점 수의 제곱만큼 칸을 쓰는 대신 두 정점이 이어졌는지를 한 번에 답하고, **인접 리스트**는 간선 수만큼만 쓰면서 이웃을 정확히 훑습니다. 게임에서 다루는 그래프는 정점이 많고 이웃은 몇 개뿐인 쪽이라 기본값은 인접 리스트입니다. 그리고 격자는 둘 중 어느 것도 아닙니다. 이웃이 좌표 계산으로 나오므로 간선을 저장하지 않습니다. 방향 배열과 범위 검사, 벽 검사 세 줄이 간선의 전부입니다.