[React, javascript] 지뢰찾기 - 빈칸 클릭 시 주변 칸 한 번에 여는 두 가지 방법 (반복문 bfs, 재귀함수 dfs)

최근 리액트 강의를 수강하며 지뢰찾기 구현을 스스로 해보았다. 지뢰찾기 게임은 사용자가 빈 칸을 클릭했을 경우 그 주변 빈칸들과 숫자칸을 전부 오픈해야한다. 

 

숫자칸이나 지뢰 칸을 클릭했을 경우는 클릭한 칸에 대한 이벤트만 처리해주면 되지만, 빈 칸을 클릭한 경우는 주변 칸 까지 모두 검사해야 하므로 조금 더 까다로운 알고리즘을 고민해봐야 했다.

 

결과적으로는 반복문과 재귀함수 두 가지 방법으로 빈칸 열기를 구현할 수 있게 되어 코드를 정리해두려고 한다.

 

사실 두 알고리즘 다 핵심 원리는 같다. 공백 칸을 클릭했을 경우, 해당 칸 근처의 여덟 칸을 검사하여 숫자 칸일 경우는 해당 칸만 오픈하고, 공백 칸일 경우는 해당 칸을 중심으로 같은 작업을 반복한다. 

 

1. 반복문과 배열을 사용해 탐색하기 (bfs)

let blankQue = []; //2차원 배열. [x,y] 좌표 저장. value가 0인 값 저장한다.
let newOpenData = [...boardOpenData];
blankQue.push([posX, posY]); 
while(blankQue.length>0) {
    let [x, y] = blankQue[0]; //대기열의 맨 앞부터 꺼내서 검사
    newOpenData[x][y]=true; //현재 검사 중인 x, y좌표
    [-1, 0 , 1].map((xp)=>{ 
        if (x+xp>=0 && x+xp<board.length) { //게임판 벗어난 좌표 걸러내기
            [-1, 0, 1].map((yp)=>{
                if (y+yp>=0 && y+yp<board[0].length) { //게임판 벗어난 좌표 걸러내기 2
                    if (board[x+xp][y+yp]==0 && newOpenData[x+xp][y+yp]==false) blankQue.push([x+xp, y+yp]);
                    //검사중인 좌표 한 칸 근처에서, 값이 0인 칸이면 검사 대기열에 추가
                    else if (board[x+xp][y+yp]>0) newOpenData[x+xp][y+yp]=true;
                    ////검사중인 좌표 한 칸 근처에서, 값이 숫자인 칸이면 바로 오픈
                }
            })
        }
    })
    blankQue.splice(0,1); //검사 끝난 맨 앞 좌표 삭제
}

 

먼저 반복문을 사용해 공백칸을 탐색하기 위해서는 공백칸의 위치를 저장할 배열이 하나 더 필요하다. 이 배열의 이름을 내 코드에서는 'blankQue'라고 지었다. 

 

newOpenData는 게임판의 오픈 유무를 저장하는 배열이다. 위 코드에서는 사용자가 처음 클릭한 칸을 중심으로 주변 여덟개의 칸을 검사하기 시작해, 공백칸이 발견되면 blankQue에 추가하고, 숫자 칸이 발견되면 newOpenData 배열에 true로 열린 칸 표시를 해주고 있다. (false가 닫힌 상태)

 

검사 작업이 끝난 후에는 검사가 끝난 blankQue 배열의 맨 앞 요소를 제거해주고, 다음 반복으로 넘어간다. 다음 검사 순서는 자연스럽게 blankQue에 저장된 다음 공백 칸이 된다. 

 

이 작업을 반복해주다보면 자연스럽게 모든 공백 칸은 blankQue에 저장되고, 더이상 검사 영역에 공백칸이 포함되어있지 않으면 자연스럽게 blankQue의 길이는 0이 되어 반복문이 끝난다. 

 

이후 newOpenData에 저장된 게임판 데이터를 랜더링에 반영해주면 된다.

 

 

2. 재귀함수를 사용해 탐색하기 (dfs)

let newOpenData = [...boardOpenData];
const useRecursive = (x, y) => {
    newOpenData[x][y]=true;
    [-1, 0 , 1].map((xp)=>{ 
        if (x+xp>=0 && x+xp<board.length) { //게임판 벗어난 좌표 걸러내기
            [-1, 0, 1].map((yp)=>{
                if (y+yp>=0 && y+yp<board[0].length) { //게임판 벗어난 좌표 걸러내기 2
                    if (board[x+xp][y+yp]==0 && newOpenData[x+xp][y+yp]==false) useRecursive(x+xp, y+yp);
                    //검사중인 좌표 한 칸 근처에서, 값이 0인 칸이면 해당 칸을 중심으로 검사 진행
                    else if (board[x+xp][y+yp]>0) newOpenData[x+xp][y+yp]=true;
                    ////검사중인 좌표 한 칸 근처에서, 값이 숫자인 칸이면 바로 오픈
                }
            })
        }
    })
}
useRecursive(posX, posY);

 

변수의 이름과 역할은 반복문을 이용한 방법에서와 동일하다. 단지 이 방법에서는 검사해야하는 공백 칸들을 저장했던 blankQue의 역할을 재귀함수가 대신하고 있을 뿐이다. 

 

사용자가 처음 클릭한 좌표를 중심으로 근처 8개의 칸을 검사하기 시작해, 공백 칸을 만나면 해당 칸의 좌표를 매개변수로 다시 useRecursive 함수를 실행한다. 공백이 아닌 칸에서는 함수가 재호출되지 않아, 재귀함수가 반복되다가 더이상 검사할 공백 칸이 없어지면 실행되었던 순서의 역순으로 함수가 종료되며 반복이 끝나게 된다.

 

남은 작업은 마찬가지로 완성된 newOpenData 게임판을 활용해 랜더링을 시키는 것 뿐이다.

 

 

- END.