LeetCode (C/C++) 529. Minesweeper

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

 

 

---

풀이

지뢰찾기를 구현하는 문제

 

클릭한 곳이 지뢰(M) -> 해당 셀만 변환

클릭한 곳이 (E)

  - 인접한 셀에 지뢰 O -> 해당 셀만 주변 지뢰 개수 정보로 변환

  - 인접한 셀에 지뢰 X -> 해당 셀 주변을 탐색하면서 변환

 

처음엔 탐색을 4방으로 했는데 8방으로 해야 했다.

 

코드 1

시작하자마자 주변 지뢰의 개수를 전부 저장하는 배열을 만들었고, 클릭된 셀부터 BFS 탐색을 하며 값을 갱신

 

코드 2

해당 풀이가 속도는 빠르나 메모리를 많이 사용하는 것 같아 탐색 중 필요할 때만 주변 지뢰의 개수를 세어 주어진 board의 값을 갱신하는 형태로 바꿈 -> 속도는 느려졌지만 메모리 사용량 감소

---

코드 1

class Solution {
public:
      void fillMineInfo(vector<vector<int>>& info, vector<vector<char>>& board) {
        int row = info.size(), col = info[0].size();

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                
                // 현재 셀이 지뢰 -> 주변 셀의 지뢰 개수 업데이트
                if (board[i][j] == 'M')
                    checkMineInfo(info, board, i, j, row, col);

                // 주어진 셀이 밝혀진 숫자 -> 주어진 지뢰 개수 저장
                else if ('1' <= board[i][j] && board[i][j] <= '8')
                    info[i][j] = board[i][j] - '0';
            }
        }
    }
    
    void checkMineInfo(vector<vector<int>>& info, vector<vector<char>>& board, int r, int c, int row, int col) {
        for (int i = max(r - 1, 0); i < min(r + 2, row); i++) {
            for (int j = max(c - 1, 0); j < min(c + 2, col); j++) {
                if (i == r && j == c)
                    continue;
                
                // 지뢰 주변의 셀이 E -> 해당 셀의 지뢰 개수 + 1
                if (board[i][j] == 'E')
                    info[i][j]++;
            }
        }
    }


    void updateRevealedBoard(vector<vector<int>>& info, vector<vector<char>>& board, int cr, int cc) {
        queue <pair<int, int>> q;
        int row = board.size(), col = board[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col));
        
        int mv[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        // 클릭한 셀의 위치부터 시작
        q.push({cr, cc});
        visited[cr][cc] = true;

        while (q.size()) {
            int r = q.front().first, c = q.front().second;
            q.pop();

            // 주어진 셀에 인접한 지뢰 존재 O -> 숫자로 변환
            if (board[r][c] != 'B' && board[r][c] != 'M' && info[r][c])
                board[r][c] = info[r][c] + '0';

            // 주어진 셀에 인접한 지뢰 존재 X -> 주변 셀 탐색하며 변환
            else if (board[r][c] != 'M'){
                board[r][c] = 'B';

                for (int i = 0; i < 8; i++) {
                    int nr = r + mv[i][0], nc = c + mv[i][1];

                    if (nr < 0 || nc < 0 || row <= nr || col <= nc || visited[nr][nc])
                        continue;
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int cr = click[0], cc = click[1];

        // 지뢰 클릭 -> 해당 지뢰만 X로 바꾼 후 반환
        if (board[cr][cc] == 'M') {
            board[cr][cc] = 'X';
            return board;
        }

        int row = board.size(), col = board[0].size();

        vector<vector<int>> mineInfo(row, vector<int>(col));
        
        // 각 셀당 인접한 지뢰 정보를 찾고 저장
        fillMineInfo(mineInfo, board);

        updateRevealedBoard(mineInfo, board, cr, cc);

        return board;
    }
};

 

코드2 -> 탐색 중 필요할 때만 CountMine

class Solution {
public:
    int countMines(vector<vector<char>>& board, int r, int c, int row, int col) {
        
        int cnt = 0;
        for (int i = max(r - 1, 0); i < min(r + 2, row); i++) {
            for (int j = max(c - 1, 0); j < min(c + 2, col); j++) {
                if (i == r && j == c)
                    continue;
                
                // 지뢰 주변의 셀이 M -> 지뢰 개수 + 1
                if (board[i][j] == 'M')
                    cnt++;
            }
        }
        return cnt;
    }

    void updateRevealedBoard(vector<vector<char>>& board, int cr, int cc) {
        queue <pair<int, int>> q;
        int row = board.size(), col = board[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col));
        
        int mv[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        // 클릭한 셀의 위치부터 시작
        q.push({cr, cc});
        visited[cr][cc] = true;

        while (q.size()) {
            int r = q.front().first, c = q.front().second;
            q.pop();


            if (board[r][c] != 'M' && board[r][c] != 'B') {
                
                // 주어진 셀에 인접한 지뢰 존재 O -> 숫자로 변환
                if ('1' <= board[r][c] && board[r][c] <= '8')
                    continue;
                
                int mineInfo = countMines(board, r, c, row, col);
                if (mineInfo) {
                    board[r][c] = mineInfo + '0';
                    continue;
                }

                // 주어진 셀에 인접한 지뢰 존재 X -> 주변 셀 탐색하며 변환
                board[r][c] = 'B';

                for (int i = 0; i < 8; i++) {
                    int nr = r + mv[i][0], nc = c + mv[i][1];

                    if (nr < 0 || nc < 0 || row <= nr || col <= nc || visited[nr][nc])
                        continue;
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int cr = click[0], cc = click[1];

        // 지뢰 클릭 -> 해당 지뢰만 X로 바꾼 후 반환
        if (board[cr][cc] == 'M') {
            board[cr][cc] = 'X';
            return board;
        }

        updateRevealedBoard(board, cr, cc);

        return board;
    }
};