Minesweeper[Array,Depth-First Search,Breadth-First Search,Matrix]

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

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

You are given an m x n char matrix board representing the game board where:

• 'M' represents an unrevealed mine,
• 'E' represents an unrevealed empty square,
• 'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
• digit ('1' to '8') represents how many mines are adjacent to this revealed square, and
• 'X' represents a revealed mine.

You are also given an integer array click where click = [clickr, clickc] represents the next click position 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. You should change it to 'X'.
2. If an empty square 'E' with no adjacent mines is revealed, then change it to a 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.

 

Example 1:

Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Example 2:

Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 50
• board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.
• click.length == 2
• 0 <= clickr < m
• 0 <= clickc < n
• board[clickr][clickc] is either 'M' or 'E'.

아.. 또 이건 뭐냐

왜 이렇게 코딩으로 게임을 짜는건지 모르겠다. 짜친다 짜쳐!!

 

문제를 읽는거부터 독해능력이 요구되는 것 -_-

 

그냥 지뢰찾기인데, 진짜 핵 귀찮다..

 

1. Python

 

근데 뭐 ,, 코딩하다보니까 또 좀 재밌다. 약간 변태적인가..? ㅎㅎ

우여곡절 끝에 풀긴했다.

 

이렇게 좀 많이 복잡한 문제의 경우, 평소처럼 Node taking 할 때 너무 처음부터 모든 걸 다 설계하려고 하면 시작조차 하기 너무 어렵다.

 

그래서 어느 정도 가다(?)만 잡고 코딩을 실행하면서 Error를 파악해 나가는 능력이 필요하다.

 

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        # Click only one time
        m = len(board)
        n = len(board[0])
        # M : unrevealed mine / E : unrevealed Empty space / Click -> M or E
        # B : revealed blank space with No adjanced mine / 1~8 : revealed with num of adjacent mine
        # X -> reveald mine : game set
        direction = [[0,1],[0,-1],[1,0],[1,1],[1,-1],[-1,0],[-1,1],[-1,-1]] # 8ea
        q = deque()
        q.append(click)
        while q :
            y,x = q.pop()
            # if click mine( click M )
            if board[y][x] == 'M':
                board[y][x] = 'X'
                break
            # if click 'E' at first time
            else:
                cnt = 0
                for i,j in direction:
                    dy = y + j
                    dx = x + i
                    # Check mine for curr status
                    if 0<=dy<m and 0<=dx<n and board[dy][dx] == 'M':
                        cnt+=1
                # Curr node is 'E' add adjacent node to queue
                if cnt==0 :
                    board[y][x] = 'B'
                    for i,j in direction:
                        dy = y + j
                        dx = x + i
                        if 0<=dy<m and 0<=dx<n and board[dy][dx] == 'E':
                            q.append([dy,dx])
                # Curr node is 'Number'
                else : board[y][x] = str(cnt)   
             
        return board

 

기나긴 코딩을 거쳤으니 모범 답안도 한 번 봐야겠다.

어쨌건 나는 queue를 이용한 것이기에 Breath First Search를 이용한 것이고, 사실 이건 Search 순서와는 상관없는 문제라 그냥 Stack을 이용한 Depth First Search를 써도 무방할 것이라 예상한다.

 

역시나 Recursive하게 풀면 코드는 짧아질 걸로 예상은 가지만.. 일단 당장 Recursive Solution은 떠오르지가 않았다.

 

뭐.. 다른 풀이를 봐도 일단 비슷하다. C++로는 다른 방법 풀이를 진행해보겠다.

 

 

2. C++

 

class Solution {
public:
    vector<vector<int>> direction = {{0,1},{0,-1},{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1}};

    int mine(vector<vector<char>>& board,int& x, int& y, int& m, int& n){
        int cnt = 0;
        for(const auto pair : direction){
            int a = pair[0];
            int b = pair[1];
            int dy = y+a;
            int dx = x+b;
            if(0<=dx && dx<n && 0<=dy && dy<m && board[dy][dx] == 'M') cnt++;
        }
        return cnt;
    }

    void dfs(vector<vector<char>>& board,int x, int y, int m, int n){
        if(!(0<=x && x<n && 0<=y && y<m && board[y][x] == 'E')) return;

        int cnt = mine(board,x,y,m,n);
        if(cnt>0){
            board[y][x] = cnt+'0';
        }else{
            board[y][x] = 'B';
            for(auto &pair : direction){
                dfs(board,x+pair[0],y+pair[1],m,n);
            }
        }

    }    

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int y = click[0];
        int x = click[1];
        if(board[y][x]=='M'){
            board[y][x] = 'X';
            return board;
        }
        dfs(board,x,y,board.size(),board[0].size());
        return board;
    }
};

 

여러 함수를 정의해서 Recursive하게 푼 것이다. 뭐.. dfs를 이렇게 recursive하게 해서 푸니까 좀 더 가독성은 좋은 거 같다.