[Leetcode] Mine Sweeper (BFS/DFS)

 

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

 

문제 파악

클릭하는 좌표가 주어지고 맵에 있는 지뢰를 찾는 문제

지뢰를 클릭하면 'X'로 바꾸고 종료, 지뢰가 아니라면 지뢰가 근처에 있을 때 '1', 근처에 없다면 'B'로 맵을 바꾸게 된다.

암시적 그래프의 탐색 문제이지만 최단거리를 찾는 문제는 아니다.

그래도 BFS 탐색이 더 편해서 BFS로 진행하였다.

---

접근 방법

1. 지뢰를 클릭하면 바로 종료
2. 탐색을 하면서 방문하면 'B'로 바꾼다.
3. 만약에 인접 노드가 지뢰라면 '1'로 표기
4. 지뢰를 체크하기 위해서 지뢰 카운트를 따로 체크하고, 체크가 되었을 경우에만 바꾸도록 지시한다.
5. 탐색을 마치면 최종 배열을 반환

---

코드 구현

import java.util.*;

class Solution {
    static int m;
    static int n;
    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;

        // 8방향 탐색
        int[] dr = {-1,1,0,0,-1,-1,1,1};
        int[] dc = {0,0,-1,1,-1,1,-1,1};

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(click);

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];

            // 지뢰면 종료
            if(board[r][c] == 'M'){
                board[r][c] = 'X';
                break;
            }

            // 지뢰 개수
            int mine = 0;
            for(int i = 0; i < 8; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];

                if(isValid(nr, nc) && board[nr][nc] == 'M') mine++;
            }
            if(mine == 0){
                board[r][c] = 'B';
                for(int i = 0; i < 8; i++){
                    int nr = r + dr[i];
                    int nc = c + dc[i];

                    if(isValid(nr, nc) && board[nr][nc] == 'E'){
                        queue.offer(new int[]{nr, nc});
                        board[nr][nc] = '0'; // 중복 방지, 방문 표시
                    }
                }
            }
            // 근처에 지뢰가 있으면 '1'로 변환
            else{
                board[r][c] = (char)('0' + mine);
            }
        }

        return board;
    }
    // 유효범위 검사
    boolean isValid(int r, int c) {
        return r >= 0 && r < m && c >= 0 && c < n;
    }
}