본문으로 건너뛰기
series develop frontend backend cs algorithm graph bfs dfs

문제를 그래프로 바꿔 보기 - 이름과 비용: 알고리즘 ep.01

지도, 사람 관계, 웹페이지 링크, 작업 의존성은 서로 다른 대상이지만 같은 구조입니다.

관계가 있으면 그래프입니다

그래프(graph) 는 정점과 간선으로 이루어진 구조입니다. 무엇을 정점으로 두고 무엇을 간선으로 볼지는 문제를 읽는 사람이 정합니다.

이 자유도 덕분에 그래프 알고리즘을 쓸 곳이 많습니다. 도시와 도로만 그래프인 게 아닙니다.

  • 미로의 각 칸이 정점, 이동 가능한 인접 칸이 간선
  • 작업이 정점, 선행 조건이 방향 간선
  • 게임의 각 상태가 정점, 한 번의 조작이 간선

마지막 항목처럼 눈에 보이는 연결이 없어도, 상태와 그 상태를 바꾸는 조작이 있으면 그래프입니다. 숫자 하나에서 시작해 더하기 빼기 곱하기로 목표 숫자에 도달하는 문제도 그래프 탐색으로 풀립니다. 정점은 숫자, 간선은 연산입니다.

세 가지 문제를 그래프로 읽는 예를 나란히 보여주는 다이어그램. 왼쪽 「미로 격자」 패널에는 3행 3열 격자가 있고 가운데 칸은 벽으로 칠해져 있음. 나머지 여덟 칸의 중앙에 작은 원(정점)이 있고 상하좌우로 이웃한 칸끼리 선(간선)으로 이어져 있으며, 아래에 「칸이 정점, 이동 가능한 인접 칸이 간선」, 「벽은 정점이 없고 간선도 없습니다」라고 적혀 있음. 가운데 「작업 의존성」 패널에는 스키마, API, 화면, 배포 네 상자가 마름모꼴로 놓여 있고 스키마에서 API와 화면으로, API와 화면에서 배포로 향하는 화살표가 있으며, 아래에 「작업이 정점, 선행 조건이 방향 간선」, 「화살표 방향이 순서를 정합니다」라고 적혀 있음. 오른쪽 「숫자 상태 공간」 패널에는 시작 2와 목표 6이 표시되고, 2에서 +1로 3, ×2로 4, 3에서 ×2로 6, 4에서 +1로 5로 이어지는 화살표가 있으며 2에서 3을 거쳐 6에 이르는 경로가 주황으로 강조됨. 아래에 「숫자가 정점, 연산 한 번이 간선」, 「2에서 6까지 최소 두 번의 연산입니다」라고 적혀 있음. 다이어그램 제목은 「관계가 있으면 그래프입니다」, 부제는 「서로 다른 세 문제를 정점과 간선으로 읽습니다」이고 하단에 「무엇을 정점으로 두고 무엇을 간선으로 볼지는 문제를 읽는 사람이 정합니다. 그래프로 읽는 순간 같은 탐색 도구를 쓸 수 있습니다」라는 문장이 있음.

개발자가 매일 쓰는 도구 중에도 그래프가 많습니다. 디렉터리와 하위 디렉터리는 트리입니다. 모듈이 서로를 import하는 관계는 방향 그래프이고, 번들러가 띄우는 순환 참조 경고는 그 그래프에서 사이클을 찾았다는 뜻입니다.

문제를 그래프로 읽는 데 성공하면 나머지는 이미 있는 도구를 고르는 일이 됩니다.

표현 두 가지를 고르는 기준

인접 리스트(adjacency list) 는 각 정점마다 이어진 정점 목록을 들고 있습니다. 인접 행렬(adjacency matrix) 은 정점 수만큼의 2차원 배열을 만들어 연결 여부를 표시합니다.

정점 4개, 간선 4개(0-1, 0-2, 1-2, 2-3)인 무방향 그래프를 인접 리스트와 인접 행렬로 표현해 나란히 비교한 다이어그램. 왼쪽 「그래프」 패널에는 정점 0, 1, 2, 3이 사각형 꼴로 놓여 있고 간선 2-3이 주황으로 강조되어 있으며 「간선 하나가 양쪽에 기록됩니다」라고 적혀 있음. 가운데 「인접 리스트 · O(V + E)」 패널에는 네 줄이 있어 0은 1과 2, 1은 0과 2, 2는 0과 1과 3, 3은 2로 이어지고, 2번 줄의 3 칸과 3번 줄의 2 칸이 주황으로 칠해져 있으며 「정점마다 이어진 정점만 적습니다」, 「칸 수 = 간선 수 × 2 = 8」이라고 적혀 있음. 오른쪽 「인접 행렬 · O(V²)」 패널에는 4행 4열 표가 있어 0행은 0 1 1 0, 1행은 1 0 1 0, 2행은 1 1 0 1, 3행은 0 0 1 0이고 2행 3열과 3행 2열의 1이 주황으로 칠해져 있으며 「모든 정점 쌍에 칸이 있습니다」, 「칸 수 = 정점 수² = 16, 대부분 0」이라고 적혀 있음. 다이어그램 제목은 「같은 그래프, 두 가지 표현」, 부제는 「정점 4개, 간선 4개(0-1, 0-2, 1-2, 2-3)인 무방향 그래프 · 간선 2-3을 색으로 따라가 봅니다」이고, 하단에 「리스트는 이어진 것만 저장하고, 행렬은 모든 쌍을 칸으로 가집니다. 정점이 십만 개면 행렬은 백억 칸입니다」, 「두 정점이 이어졌는지 확인하는 비용은 행렬이 O(1), 리스트가 O(차수)입니다. 밀도가 선택을 정합니다」라는 두 문장이 있음.

인접 리스트인접 행렬
공간O(V + E)O(V²)
두 정점 연결 확인O(차수)O(1)
한 정점의 이웃 순회O(차수)O(V)
간선 추가O(1)O(1)

선택 기준은 밀도입니다.

대부분의 실제 그래프는 희소(sparse) 합니다. 정점이 십만 개여도 각 정점이 이어진 곳은 몇 개뿐입니다. 이럴 때 인접 행렬은 백억 칸을 잡아놓고 대부분을 0으로 채웁니다. 이럴 때는 인접 리스트가 맞습니다.

인접 행렬이 유리한 경우도 있습니다. 정점이 수백 개 이하로 적으면서 두 정점이 이어졌는지를 자주 물어야 할 때입니다. 전체 쌍 최단 거리를 구하는 상황이 대표적입니다.

실무에서 그래프를 다루는 도구는 대부분 인접 리스트 쪽입니다. 패키지 관리자가 의존성 트리를 출력하거나 번들러가 모듈 그래프를 만들 때, 모듈 하나가 직접 의존하는 목록만 들고 있으면 충분하기 때문입니다.

// 인접 리스트: 무방향 그래프
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
  graph[u].push(v);
  graph[v].push(u); // 방향 그래프면 이 줄을 뺀다
}

격자는 이미 그래프입니다

2차원 배열로 주어진 지도는 간선을 명시하지 않아도 그래프입니다. 인접한 칸이 간선이니 방향 배열만 두면 됩니다.

const dr = [-1, 1, 0, 0]; // 상하좌우
const dc = [0, 0, -1, 1];

for (let d = 0; d < 4; d++) {
  const nr = r + dr[d];
  const nc = c + dc[d];
  if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // 범위 밖
  // nr, nc가 이웃 칸
}

대각선까지 포함해야 하면 배열을 여덟 개로 늘립니다. 범위 검사는 반복문 안에서 먼저 해야 합니다. 이 검사를 빠뜨려 생기는 인덱스 오류가 격자 문제에서 가장 흔한 실수입니다.

깊이 우선과 너비 우선은 다른 질문에 답합니다

두 탐색의 차이는 지금 보고 있는 것 다음에 어디를 볼지 고르는 방식에 있습니다.

깊이 우선 탐색(depth first search) 은 갈 수 있는 데까지 들어갔다가 막히면 돌아 나옵니다. 스택으로 동작하고 재귀로 쓰면 코드가 짧습니다.

너비 우선 탐색(breadth first search) 은 현재 위치에서 한 칸 거리의 모든 곳을 먼저 보고, 그다음 두 칸 거리를 봅니다. 큐로 동작합니다.

같은 격자에서 깊이 우선 탐색과 너비 우선 탐색의 방문 순서를 비교한 다이어그램. 왼쪽은 깊이 우선 탐색으로, 4행 4열 격자에서 왼쪽 위 시작 칸부터 번호가 매겨지며 한 방향으로 끝까지 내려갔다가 되돌아오는 경로가 곡선 화살표로 이어짐. 방문 번호는 1부터 시작해 한쪽 가지를 모두 채운 뒤 다른 가지로 넘어가는 순서를 보임. 오른쪽은 너비 우선 탐색으로, 같은 격자에서 시작 칸을 중심으로 동심원 형태의 층이 형성되며 거리 1인 칸들이 같은 색, 거리 2인 칸들이 다음 색으로 칠해짐. 각 칸에는 시작점으로부터의 거리가 숫자로 적혀 있음. 왼쪽 패널 머리글은 「DFS · 한 방향으로 끝까지」이고 격자 옆에 「되돌아오는 지점이 생깁니다」, 아래에 「경로가 있는지, 몇 덩어리인지 판별할 때」라는 라벨이 붙어 있음. 오른쪽 패널 머리글은 「BFS · 가까운 곳부터 층으로」이고 「숫자는 시작점으로부터의 거리입니다」, 「최단 거리를 물을 때, 단 간선 비용이 모두 같을 때만」이라는 라벨이 붙어 있음. 다이어그램 제목은 「같은 격자, 같은 시작점인데 순서만 다릅니다」, 부제는 「둘 다 모든 칸을 한 번씩 봅니다. 무엇을 보장하느냐가 다릅니다」임. 하단 정리에는 「무엇을 보장받아야 하는지로 고릅니다」라는 머리글 아래, DFS는 재귀로 짧게 쓰지만 깊이가 깊으면 스택이 넘치고 방문 순서에 의미가 없다는 것과 BFS는 큐가 필요해 메모리를 더 쓰지만 먼저 도착한 경로가 최단이라는 것을 보장한다는 설명이 적혀 있음.

무엇을 물었느냐로 고릅니다.

  • 두 지점이 이어져 있는가, 덩어리가 몇 개인가, 모든 경로를 나열하라: 깊이 우선
  • 최소 몇 번 만에 도달하는가: 너비 우선

고르는 기준은 실무에서도 같습니다. 디렉터리를 훑어 조건에 맞는 파일을 찾거나 모듈 사이의 순환 참조를 잡을 때는 깊이 우선을 씁니다. 친구의 친구까지 몇 다리 만에 닿는지 세거나 화면 사이의 최소 이동 횟수를 구할 때는 너비 우선을 씁니다.

너비 우선이 최단 거리를 주는 근거

너비 우선 탐색이 처음 도달했을 때의 거리가 최단이라는 보장에는 조건이 있습니다. 모든 간선의 비용이 같아야 합니다.

이유는 탐색 순서에 있습니다. 거리 1인 정점을 모두 큐에 넣고, 그것들을 꺼내면서 거리 2인 정점을 넣습니다. 큐는 먼저 들어온 것이 먼저 나오므로 거리가 작은 정점부터 처리됩니다. 어떤 정점에 처음 도달했다면 그보다 짧은 경로는 이미 확인되었다는 뜻입니다.

간선마다 비용이 다르면 이 논리가 무너집니다. 간선 하나로 가는 길이 간선 세 개로 가는 길보다 비쌀 수 있기 때문입니다. 그때는 ep.04 가중치와 순서와 연결성의 다익스트라를 씁니다.

function shortestPath(grid, start, target) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));

  const queue = [start];
  let head = 0; // shift 대신 읽기 위치를 옮긴다
  dist[start[0]][start[1]] = 0;

  const dr = [-1, 1, 0, 0];
  const dc = [0, 0, -1, 1];

  while (head < queue.length) {
    const [r, c] = queue[head++];
    if (r === target[0] && c === target[1]) return dist[r][c];

    for (let d = 0; d < 4; d++) {
      const nr = r + dr[d];
      const nc = c + dc[d];
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1) continue;       // 벽
      if (dist[nr][nc] !== -1) continue;      // 이미 방문
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
  return -1; // 도달 불가
}

shift() 대신 읽기 위치를 옮기는 이유는 자료구조 시리즈 ep.02 배열과 해시의 진짜 비용에서 다뤘습니다. 격자가 커질수록 이 차이가 그대로 실행 시간이 됩니다.

방문 표시를 큐에 넣는 시점에 하는 것도 중요합니다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어가 중복 처리됩니다.

재귀 깊이에는 현실적인 제약이 있습니다

깊이 우선 탐색을 재귀로 쓰면 코드가 짧고 읽기 좋습니다. 대신 호출 스택을 씁니다.

정점이 십만 개인 그래프가 한 줄로 이어져 있으면 재귀 깊이도 십만이 됩니다. 자바스크립트 엔진의 스택 한계를 넘어 오류가 납니다. 이 한계는 엔진과 실행 환경에 따라 다르고 명세로 정해진 값이 아닙니다.

깊이가 클 수 있는 상황이라면 명시적 스택으로 바꿔야 합니다.

function dfsIterative(graph, start) {
  const visited = new Set([start]);
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    for (const next of graph[node]) {
      if (visited.has(next)) continue;
      visited.add(next);
      stack.push(next);
    }
  }
  return visited;
}

방문 순서는 재귀 버전과 달라질 수 있습니다. 재귀는 이웃 목록의 첫 번째부터 들어가지만, 명시적 스택은 마지막에 넣은 것을 먼저 꺼내므로 목록의 마지막 이웃부터 방문합니다. 정점 0의 이웃이 1, 2, 3이면 재귀는 1로, 명시적 스택 버전은 3으로 먼저 갑니다. 사전순으로 가장 앞선 경로를 구하는 문제처럼 순서가 답에 영향을 주면, 이웃을 넣을 때 [...graph[node]].reverse()처럼 순서를 뒤집어 재귀와 같은 순서로 맞춰야 합니다.

참고 자료

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

다음 편 예고

ep.02 - 탐색 공간을 줄이는 근거

절반을 버려도 답이 남는다는 확신은 어디서 오는지 봅니다. 이분탐색의 전제인 단조성에서 출발해 답 자체를 이분탐색하는 방법, 투 포인터, 백트래킹의 가지치기까지 하나의 관점으로 묶습니다.