지뢰찾기를 최적화해주다. (Feat. DFS vs BFS)

📝 본 포스트에서는 지뢰찾기 클론 프로젝트에서 예기치 못한 에러를 발견하고 최적화를 해주었던 이야기를 기록한다.

지뢰찾기는 원본 게임을 한번도 해본 적이 없어 초반 고전했던 프로젝트였다. 그러나 QA를 하면서 푹 빠지게 되어 5분 10분씩 붙잡고 있는 나 자신을 발견하게 되더라. 심플하면서도 미친듯이 중독성이 있는게 테트리스 뺨 치는 정말 지니어스한 게임이 아닌가 한다.

지뢰찾기에서는 빈칸을 누를 경우 해당 칸 위에 주변에 폭탄이 몇개인지 표시되게 되는데, 폭탄이 없는 경우는 엣지까지 주변을 탐색하여 열어야 하는 기능이 존재해야한다.

위의 이미지처럼 파란 점이 있는 칸을 누를 경우 1, 2, 3... 등의 숫자가 표시된 "엣지"들이 나타날때까지 연쇄적으로 빈칸들을 함께 열어주어야 하는 것이다.

먼저 탐색로직을 작성할 함수명을 revealZeroCluster라고 명명해주고 주변의 이웃된 "팔방"은 상수화하여 NEIGHBORS에 저장해주었다.

export const NEIGHBORS = [
  { x: -1, y: 0 },
  { x: 1, y: 0 },
  { x: 0, y: -1 },
  { x: 0, y: 1 },
  { x: -1, y: -1 },
  { x: 1, y: 1 },
  { x: 1, y: -1 },
  { x: -1, y: 1 },
] as const;

초기에 작성해준 탐색로직은 다음과 같다.

1️⃣: DFS with recursive fn

import { NEIGHBORS } from "../constant";
import { Matrix } from "../types/type";

function revealZeroCluster(
  clickedX: number,
  clickedY: number,
  gameMatrix: Matrix,
) {
  const modifiedMatrix = [...gameMatrix.map(row => [...row])];
  const visitedCells: Set<string> = new Set();
  // 이미 방문했는지 여부를 파악하기 위한 Set

  function revealZeroDFS(x: number, y: number) {
    if (
      x < 0 ||
      x >= modifiedMatrix.length ||
      y < 0 ||
      y >= modifiedMatrix[x].length
    ) {
      return;
    }
	// 탐색 대상 칸이 보드의 범위에서 벗어난 경우 return

    if (visitedCells.has(`${x}-${y}`)) {
      return;
    }
	// 탐색 대상 칸을 이미 방문한 경우 return

    if (modifiedMatrix[x][y].value !== 0) {
      modifiedMatrix[x][y].status = "open";

      return;
    }
    // 탐색 대상 칸이 0이 아닌 엣지인 경우 오픈해주고 return
    
    // 위 얼리리턴 조건에 모두 걸리지 않는경우...

    visitedCells.add(`${x}-${y}`);
    // 방문기록 남겨주고

    modifiedMatrix[x][y].status = "open";
    // 칸을 오픈해주고

    NEIGHBORS.forEach(neighbor => {
      const newX = x + neighbor.x;
      const newY = y + neighbor.y;
      revealZeroDFS(newX, newY);
      // 계속해서 탐색 진행
    });
  }

  revealZeroDFS(clickedX, clickedY);

  return modifiedMatrix;
}

export default revealZeroCluster;

깔끔하게 잘 동작해주는 모습이다.
익숙한 게임임에도 불구하고 내가 직접 짠 로직을 통해 촥! 펼쳐지는 것을 보니 쾌감이 있다.

다만 이 게임에는 커스텀 레벨 기능이 있어 최대 100 x 100의 10000개의 빈칸까지 생성이 가능하다.
거대한 판을 만들고 클릭하자 예기치 못한 에러가 발생하게 되는데..

maximum call stack size exceeded! 🤦‍♀️

콜스택이 아닌 큐를 사용하는 BFS 로직으로 이 문제를 고쳐보자.

2️⃣: BFS with queue

import { NEIGHBORS } from "../constant";
import { Matrix } from "../types/type";

function revealZeroCluster(
  clickedX: number,
  clickedY: number,
  gameMatrix: Matrix,
) {
  const modifiedMatrix = [...gameMatrix.map(row => [...row])];
  const queue: { x: number; y: number }[] = [];

  queue.push({ x: clickedX, y: clickedY });

  while (queue.length > 0) {
    const currentCell = queue.shift();

    if (!currentCell) {
      continue;
    }

    const { x, y } = currentCell;

    if (
      x < 0 ||
      x >= modifiedMatrix.length ||
      y < 0 ||
      y >= modifiedMatrix[x].length ||
      modifiedMatrix[x][y].status === "open"
    ) {
      continue;
    }
	// 탐색 대상 칸이 보드의 범위에서 벗어나있거나 이미 "open"인 경우 continue

    if (modifiedMatrix[x][y].value !== 0) {
      modifiedMatrix[x][y].status = "open";
      continue;
    }
	// 탐색 대상 칸이 0이 아닌 엣지인 경우 열어주고 continue

    modifiedMatrix[x][y].status = "open";
	// 탐색 대상 칸 오픈

    NEIGHBORS.forEach(neighbor => {
      const newX = x + neighbor.x;
      const newY = y + neighbor.y;
      queue.push({ x: newX, y: newY });
      // 큐의 맨 뒤에 탐색 대상 칸 추가. 재귀가 아니기 때문에 점점 사방으로 범위를 넓혀가며 탐색하게 된다.
    });
  }

  return modifiedMatrix;
}

export default revealZeroCluster;

이 로직을 적용해본 후 다시 run dev해서 확인해보면?

콜스택을 활용하는 로직이 아니므로 탐색 대상이 많은 경우에도 문제가 일어나지 않는다!

교훈

게임 개발에서는 헤비한 뎁스 연산이 있을 수 있으며,
레벨 디자인의 확장성을 고려하면 스택을 이용하는 재귀로직은 피하는게 좋다.

마무리

지뢰찾기 클론은 서비스성 프로젝트와는 또 다른 디렉토리 구조와 아키텍쳐로 접근해야하기 때문에 구현하며 무척 즐거웠다. 또한 알고리즘 문제풀이에서 자주 등장했던 matrix나, 재귀를 이용한 탐색 등을 실제 환경에 도입할 수 있는 점에서 공부의 의의를 찾을 수 있어서 뜻 깊었다.

게임개발은 특히 "상태", 그리고 "레벨"을 내가 스스로 정의하는 것, 각 로직들이 그러한 전역 값들을 바라보고 동분서주하도록 구현하는 것이 흥미롭다. 신이 된 것처럼 "세계"과 "상황"을 만들어낸다는 감각이 개발자로 하여금 아드레날린이 나도록 하는 것 같다.

컴퓨터실에서 지뢰찾기보다는 스파이더를 자주 했었는데, 다음은 스파이더를 만들어볼까도 싶다.