[알고리즘/자바스크립트] 지뢰찾기 알고리즘 (Minesweeper Algorithm)

 

 

며칠 전에 거의 일주일을 고생하며 구현한 지뢰찾기 게임이다.

오늘은 지뢰찾기 구현할 때 가장 핵심이 되는 알고리즘 2가지를 정리해보려고 한다.

 

 

 

1. 임의의 칸에 지뢰 배분하기

먼저 9X9 사이즈의 칸에 10개의 지뢰를 배분한다고 해보자.

우리는 먼저 아래와 같이 생긴 9X9의 빈 방을 만들어야할 것이다.

 

 

이 것을 2차 배열로 만들어준다.

 

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0]

 

초기에 빈 방에 든 값은 0이다. 0은 아무것도 없는 상태를 의미한다.

이 방은 row와 col 모두 0~8까지의 방 번호(index)를 가진다.

그러므로 첫번째 줄의 첫번째 칸은 (0, 0)이란 방 번호를 가지고

마지막 줄의 마지막 칸은 (8, 8)이란 방 번호를 가진다.

 

 

이제 우리가 할 일은 0~8 사이의 랜덤 숫자를 2개씩 뽑아서

그 랜덤 숫자를 방 번호로 하여 해당 방에 지뢰를 심어주는 것이다.

여기서 랜덤 숫자는 중복값이 나오지 않도록 한다.

 

					m
	m
								m
			m	m
	m					m
						m
			m

 

지뢰가 다 배치되었다면 이제 모든 칸을 검색하면서 해당 칸의 양 사방 칸에 들어있는

지뢰의 숫자를 센 다음, 그 숫자를 표시한다.

 

만약에 아래 칸에서 빨간색으로 칠한 칸에 숫자를 넣는다면 

노란색 영역을 검사한 후 노란색 영역에 들어있는 지뢰 숫자를 카운트한 값 2를 넣어야한다.

 

	1	2	2
	2	m	m
	2	m	3
	1	1	1

 

function placeMines (mLen, row, col, x, y) {
  for (let i = 0; i < row; i++) {
    INIT.board.push([]);
    for (let j = 0; j < col; j++) {
      INIT.board[i].push(0);
    }
  }
  for (let i = 0; i < mLen; i++) {
    let rd1 = Math.floor(Math.random() * row);
    let rd2 = Math.floor(Math.random() * col);
    if (INIT.board[rd1][rd2] || INIT.board[x][y]) {
      i--;
    } else {
      INIT.board[rd1][rd2] = 'm';
    }
  }
  for (let i = 0; i < INIT.board.length; i++) {
    for (let j = 0; j < INIT.board[i].length; j++) {
      if (INIT.board[i][j] !== 'm') {
        INIT.board[i][j] = countMines(i, j, INIT.board);
      }
    }
  }
  function countMines (in1, in2, arr) {
    let cnt = 0;
    let iLen = in1 + 2;
    let jLen = in2 + 2;
    for (let i = in1 - 1; i < iLen; i++) {
      for (let j = in2 - 1; j < jLen; j++) {
        if (i < 0 || j < 0 || i > arr.length - 1 || (i === in1 && j === in2)) {
          continue;
        }
        if (arr[i][j] === 'm') {
          cnt++;
        }
      }
    }
    return cnt;
  }
}

 

위 로직대로 구현한 코드이다.

 

근데 위 로직대로 구현하면 처음에 빈 방을 만들 때 반복문을 사용하고,

랜덤한 방번호를 뽑아서 지뢰를 배분할 때 다시 반복문을 사용하고,

마지막으로 칸마다 반복하여 지뢰 숫자를 카운트할 때 또 반복문을 사용해야한다.

 

이 과정을 줄일 수 있는 방법이 없을까하여 생각해낸 방법이 아래 방법이다.

 

 

랜덤한 방에 지뢰를 배분하는 순간,

그 방의 양 사방에 숫자 1을 더한다.

 

1	1	1
1	m	1
1	1	1

 

1	1	1
1	m	1
1	1	2	1
		1	m

 

이렇게 하면 배분을 다 끝내는 순간 숫자도 모두 결정된다.

 

function placeMines (mLen, row, col, tdIndex) {
  let x = Math.floor(tdIndex / INIT.defCol);
  let y = tdIndex % INIT.defCol;
  for (let i = 0; i < row; i++) {
    INIT.board.push([]);
    for (let j = 0; j < col; j++) {
      INIT.board[i].push(0);
    }
  }

  for (let i = 0; i < mLen; i++) {
    let rd1 = Math.floor(Math.random() * row);
    let rd2 = Math.floor(Math.random() * col);
    if (INIT.board[rd1][rd2] === 'm' || (rd1 === x && rd2 === y)) {
      i--;
    } else {
      INIT.board[rd1][rd2] = 'm';
      countMines(rd1, rd2, INIT.board);
    }
  }
  INIT.boardFlat = [].concat.apply([], INIT.board);

  function countMines (in1, in2, arr) {
    let iLen = in1 + 2;
    let jLen = in2 + 2;
    for (let i = in1 - 1; i < iLen; i++) {
      for (let j = in2 - 1; j < jLen; j++) {
        if (i < 0 || j < 0 || i === arr.length || j === arr[i].length || (i === in1 && j === in2)) {
          continue;
        }
        arr[i][j] += (arr[i][j] !== 'm') ? 1 : '';
      }
    }
  }
}

 

 

 

 

2. 빈 칸을 클릭했을 때 주변 모든 빈 칸을 연쇄적으로 오픈하기

이 부분에서 정말 어마어마하게 헤맸는데

재귀 호출을 사용하여 해결했다.

 

빈 칸을 클릭하는 순간 해당 칸을 오픈한 후,

해당 칸의 양 사방의 8개 칸을 검사하여

지뢰가 하나도 없는 경우 8개 칸에 대하여 다시 재귀 호출한다.

 

그러면 8개 칸 또한 본인의 양 사방을 검사할 것이고

지뢰가 하나도 없으면 다시 본인 칸의 8개 칸에 대하여 재귀 호출한다.

 

function findEmptySquare (tdIndex, x, y) {
  $td[tdIndex].classList.add('clicked');
  if (INIT.board[x][y] !== 0) {
    $td[tdIndex].classList.add(`txt-${INIT.board[x][y]}`);
    $td[tdIndex].textContent = INIT.board[x][y];
  }
  INIT.squareLen--;
  INIT.board[x][y] = 'o';

  let iLen = x + 2;
  let jLen = y + 2;
  let noMine = true;

  for (let i = x - 1; i < iLen; i++) {
    for (let j = y - 1; j < jLen; j++) {
      if (i < 0 || j < 0 || i === INIT.board.length || j === INIT.board[i].length || (i === x && j === y) || INIT.board[i][j] === 'o') {
        continue;
      }
      if (INIT.board[i][j] === 'm') {
        noMine = false;
      }
    }
  }

  if (noMine) {
    for (let i = x - 1; i < iLen; i++) {
      for (let j = y - 1; j < jLen; j++) {
        if (i < 0 || j < 0 || i === INIT.board.length || j === INIT.board[i].length || (i === x && j === y) || INIT.board[i][j] === 'o') {
          continue;
        }
        findEmptySquare(i * INIT.defCol + j, i, j);
      }
    }
  }
}

 

 

 

 

 

 

전체 코드는 gitlab에 올려두었다.

 

https://gitlab.com/jy7123943/minesweeper.git

Juyeon / Minesweeper