기억하고싶은것들

Let's play the minesweeper game (Wikipedia, online game)!

You are given a 2D char matrix representing the game board. 'M' represents an unrevealedmine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:

1. If a mine ('M') is revealed, then the game is over - change it to 'X'.
2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

지뢰 찾기 게임을 플레이하자!

2차원의 char 배열이 주어진다.

• 'M'은 플레이어가 지뢰라고 표시해 놓은 칸
• 'E'는 눌러지지 않는 칸
• 'B'는 아무것도 없는 칸
• '숫자'는 주변에 인접한 지뢰의 개수
• 'X'는 지뢰 

다음으로, 누를 지점의 값을 input으로 입력을 받는다

그 후에 2차원 char 배열의 결과를 반환하라.

1. 만약, 'M'이 눌리면 'X'로 변환하고 게임 끝
2. 만약, 주변에 지뢰가 하나도 없는 'E'가 눌리면, 'B'로 바뀌고 해당 인접한 칸의 값을 변환
3. 만약, 주변에 지뢰가 하나 이상 있는 'E'가 눌리면, 숫자로 바꾼다.
4. 더 이상 표현할 수 있는 칸이 없을 때 2차원 배열을 반환하라

지뢰 찾기는 주변에 인접한 칸들을 방문하며 문제를 풀어가는 특징이 있다.

이러한 문제는 기존에 Graph의 Level (인접한 레벨) 별로  방문하는 BFS로 해결할 수 있다.

graph에서는 자신의 child를 방문했다면, 2차원의 배열에서는 자신에 인접한 칸들을 방문하면 된다. 

int [] dx = new int[] { 0, -1, 0, 1, 1, -1, 1, -1 };
int[] dy = new int[] { 1, 0, -1, 0, 1, -1, -1, 1 };

주변에 인접한 칸들이 방문 가능한 칸인지 판별하고, 방문이 가능하다면 queue에 담아서 순차적으로 방문을 하면 된다. 

또한, 중복적으로 방문한 칸을 들리지 않기 위해서 방문한 칸들을 기록하는 2차원의 배열을 두면 무한 반복을 막을 수 있다.

    public char[][] updateBoard(char[][] board, int[] click) {

        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];

        queue.offer(click);
        visited[click[0]][click[1]] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int mines = getNumberOfMines(board, x, y);

            if (mines == 0) {
                board[x][y] = 'B';

                for (int i = 0; i < 8; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    // Check adjacent cell visitable or not 
                    if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length && !visited[nx][ny]) {
                        queue.offer(new int[] { nx, ny });
                        visited[nx][ny] = true; // Check this cell visited 
                    }
                }
            } else {
                board[x][y] = (char) (mines + '0');
            }
        }

        return board;
    }

추가적으로, 해당 셀 주변에 지뢰가 몇 개 있는지 판별하는 메서드를 따로 두었다.

    private int getNumberOfMines(char[][] board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
                cnt += board[nx][ny] == 'M' ? 1 : 0;
            }
        }
        return cnt;
    }

문제 출처 :

leetcode.com/problems/minesweeper/