[리트코드] 529. Minesweeper

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

문제를 읽어보면 지뢰찾기 게임의 규칙과 같다는 것을 알 수 있다. 

주어진 위치에서 부터 탐색해 나가면서 탐색한 위치에 알맞는 문자로 업데이트 해준다.

"E" 일 경우는 아직 탐색하지 않았으니 탐색한다음 알맞는 문자로 변경해주고 E가 아닌 경우에는 이미 탐색했으니 탐색할 필요가 없다.

 

탐색하는 경우를 그려보면 위와 같이 나타난다.

BFS 로 탐색하면 될 거 같다.

 

시간 복잡도를 계산해보면

해당 한번 탐색한 위치를 다시 탐색하지 않기 때문에 아무리 많이 탐색해도 그래프를 전부 탐색하는 것이 끝이다.

따라서 n * m 이 된다.

 

코드

public class Minesweeper {
    public static void main(String[] args){
        char[][] board = {{'E', 'E', 'E', 'E', 'E'}, {'E', 'E', 'M', 'E', 'E'}, {'E', 'E', 'E', 'E', 'E'}, {'E', 'E', 'E', 'E', 'E'}};
        int[] click = {3, 0};

        char[][] result = updateBoard(board, click);

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

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

        Queue<int[]> queue = new LinkedList<>();

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

        if (board[click[0]][click[1]] != 'E') {
            return board;
        }

        queue.offer(click);

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

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            check(board, cur);
            for (int[] move : moves) {
                int curX = cur[0] + move[0];
                int curY = cur[1] + move[1];

                if (curX >= 0 && curX < board.length && curY >= 0 && curY < board[0].length) {
                    if (board[curX][curY] == 'E' && board[cur[0]][cur[1]] == 'B') {
                        queue.offer(new int[]{curX, curY});
                    }
                }
            }
        }

        return board;
    }

    public static void check(char[][] board, int[] click) {

        int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        int cnt = 0;

        for (int[] dir : directions) {
            int curX = click[0] + dir[0];
            int curY = click[1] + dir[1];

            if (curX >= 0 && curX < board.length && curY >= 0 && curY < board[0].length) {
                if (board[curX][curY] == 'M') {
                    cnt++;
                }
            }
        }

        if (cnt == 0) {
            board[click[0]][click[1]] = 'B';
        }else{
            board[click[0]][click[1]] = Integer.toString(cnt).charAt(0);
        }
    }
}

 

배움점

int 자료형을 char 자료형으로 바꾸는 방법이 헷갈렸다.

Integer.toString(cnt).charAt(0);