(Leet Code JS)Minesweeper

https://leetcode.com/problems/minesweeper/

Minesweeper - LeetCode

DFS를 이용한 문제풀이.

 

탐색에 필요한 변수와 배열을 미리 선언한다.

또한, 탐색 시 board의 범위를 벗어나는지 검사하는 checkRange도 정의.

 

dfs함수에는 탐색할 x, y 좌표를 받아 8방향을 검사하면 된다.

dfs() 시작은 board[x][y] 좌표에 방문했다는 표시로 visited[x][y] = true로 바꿔준다.

종료조건은 좌표가 "M"이면 "X"로 바꿔주고 리턴하면된다.

 

 

다음에 방문할 좌표가 "B"인지 확인하는 isBlank,

현재 좌표 주변에 있는 지뢰의 갯수를 나타내는 count,

주변에 지뢰가 없을 때, 방문하는 좌표의 후보를 저장하는 next를 이용해 8방향 검사를 한다.

 

방문할 다음 좌표의 범위가 벗어나는지 checkRange 함수로 검사한다.

벗어나지 않으며 방문한 적이 없는 좌표라면 다음 두 가지 조건을 더 확인한다.

다음 방문할 좌표의 문자가 "E"라면 next 배열에 push.

그렇지 않고 문자가 "M"이라면 count++과 isBlank를 false로 바꿔준다.

 

8방향 검사가 끝나면 isBlank를 통해 dfs를 더 진행할지 결정한다.

true라면 board[x][y] = "B"로 바꾼 후, next에 담겨있는 모든 좌표를 dfs 한다.

 

그렇지 않다면 지뢰가 주변에 있다는 뜻이 되므로

board[x][y]를 count로 바꿔주면 된다.

 

const updateBoard = (board, click) => {
    const queue = [];
    const m = board.length;
    const n = board[0].length;
    const directX = [-1, -1, 0, 1, 1, 1, 0, -1];
    const directY = [0, 1, 1, 1, 0, -1, -1, -1];
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const answer = Array.from({length: m}, () => Array(n).fill("E"));
    
    const checkRange = (x, y) => x >= 0 && x < m && y >= 0 && y < n;
    
    const dfs = (x, y) => {
        visited[x][y] = true;
        
        if(board[x][y] === "M"){
            board[x][y] = "X";
            return;
        }
        
        let isBlank = true;
        let count = 0;
        const next = [];
        
        for(let i = 0; i < 8; i++){
            const nx = x + directX[i];
            const ny = y + directY[i];
            
            if(checkRange(nx, ny) && !visited[nx][ny]){
                if(board[nx][ny] === "E"){
                    next.push([nx, ny]);
                } else if(board[nx][ny] === "M"){
                    count++;
                    isBlank = false;
                }
            }
        }
        
        if(isBlank){
            board[x][y] = "B";
            
            for(let i = 0; i < next.length; i++){
                dfs(next[i][0], next[i][1]);
            }
        } else{
            board[x][y] = count.toString();
        }
    }
    
    dfs(click[0], click[1]);
    
    return board;
};