[리트코드] 529 - Minesweeper

529. Minesweeper

Medium

---

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'.

분류

배열, 깊이 우선 탐색, 너비 우선 탐색, 행렬

---

문제 풀이

문제 분석

이 문제는 지뢰찾기 게임의 한 턴을 시뮬레이션하는 것입니다.
입력으로 게임 보드(board)와 클릭한 위치(click)가 주어집니다. 보드는 'M'(지뢰), 'E'(미공개 빈 칸), 'B'(공개된 빈 칸), '1'~'8'(주변 지뢰 수), 'X'(공개된 지뢰) 문자로 구성됩니다.
규칙에 따라 클릭한 위치를 공개하고, 연쇄적으로 공개되어야 할 칸들을 모두 업데이트한 최종 보드를 반환해야 합니다.

접근 방법

너비 우선 탐색(BFS) 알고리즘을 사용했습니다.
이유는 다음과 같습니다.

1. 클릭한 위치에서 시작하여 인접한 칸들을 단계적으로 탐색해야 합니다.
2. 주변에 지뢰가 없는 칸('B')일 경우에만 인접한 미공개 칸('E')을 큐에 넣어 계속 탐색을 이어가야 합니다.
3. 큐(Queue) 자료구조를 사용하면 현재 공개된 칸에서 인접 칸들을 순차적으로 처리하기에 적절합니다.
   또한, **방문 배열(visited)**을 따로 두어 이미 처리한 칸을 다시 큐에 넣지 않도록 하여 중복 연산을 방지하고 무한 루프를 예방했습니다.

구현 설명

1. 초기 클릭 처리 및 지뢰 클릭 시 예외 처리

• 클릭 좌표(cx, cy)를 꺼냅니다.
• 해당 위치가 지뢰('M')라면 즉시 'X'로 변경하고 보드를 반환하여 게임을 종료시킵니다.

2. BFS 탐색 준비

• 방문 여부를 기록할 2차원 배열 visited를 생성하고, 시작 위치를 True로 표시합니다.
• 8방향(상하좌우, 대각선) 탐색을 위한 방향 배열 check_x, check_y를 정의합니다.
• 시작 좌표를 큐(deque)에 넣고 탐색을 시작합니다.

3. 큐 순회 및 주변 지뢰 개수 세기

• 큐에서 좌표 (x, y)를 꺼냅니다.
• 8방향으로 인접 칸을 확인하며 보드 범위 내에 있고 지뢰('M')인 칸의 개수(cnt)를 셉니다.

4. 지뢰 개수에 따른 칸 업데이트 및 탐색 확장

• 주변 지뢰가 0개인 경우 (cnt == 0):
  • 현재 칸을 'B'로 변경합니다.
  • 다시 8방향을 돌며, 범위 내에 있고 **미방문 상태이며 미공개 빈 칸('E')**인 인접 칸들을 큐에 추가하고 방문 처리합니다. (연쇄 공개)
• 주변 지뢰가 1개 이상인 경우 (cnt > 0):
  • 현재 칸을 숫자 문자열(str(cnt))로 변경합니다.
  • 인접 칸을 큐에 넣지 않고 탐색을 중단합니다. (숫자 칸에서는 더 이상 확장하지 않음)

⏱복잡도 분석

• 시간 복잡도: O(m × n)
  m은 행의 수, n은 열의 수입니다. 최악의 경우 보드 전체 칸을 한 번씩 방문하며, 각 칸에서 상수 연산(8방향 확인)을 수행하므로 O(m × n)입니다.
• 공간 복잡도: O(m × n)
  방문 배열 visited가 O(m × n) 크기를 차지하고, 큐 역시 최악의 경우 모든 칸이 들어갈 수 있어 O(m × n)의 추가 공간이 필요합니다.

핵심 포인트

1. 클릭 즉시 지뢰('M')면 게임 종료: 별도 탐색 없이 'X'로 바꾸고 바로 리턴해야 합니다.
2. 'E'에서 'B'로 바뀔 때만 BFS 확장: 주변 지뢰가 0개여야 인접 칸을 큐에 넣습니다. 숫자가 표시되는 칸('1'~'8')은 탐색의 끝 지점이 됩니다.
3. 방문 배열(visited) 필수: 방문 처리를 큐에 넣을 때(append 시점)에 해야 중복 삽입을 막을 수 있습니다. 꺼낼 때(popleft 시점)에 하면 같은 칸이 큐에 여러 번 들어갈 수 있습니다.

풀이 코드

from collections import deque

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        n = len(board)
        m = len(board[0])

        cx,cy = click
        if board[cx][cy] == "M":
            board[cx][cy] = "X"
            return board

        visited =[[False] * m for i in range(n)]
        visited[cx][cy] = True
        check_x = [-1,0,1]
        check_y = [-1,0,1]

        queue = deque([(cx,cy)])
        while queue:
            x,y = queue.popleft()
            cnt = 0
            for dx in check_x:
                for dy in check_y:
                    sx,sy = x+dx,y+dy
                    if 0<=sx<n and 0<=sy<m:
                        if board[sx][sy] == "M":
                            cnt += 1

            if cnt == 0:
                board[x][y] = "B"
                for dx in check_x:
                    for dy in check_y:
                        sx,sy = x+dx,y+dy
                        if 0<=sx<n and 0<=sy<m and not visited[sx][sy] and board[sx][sy] == "E":
                            queue.append((sx,sy))
                            visited[sx][sy] = True
            
            else:
                board[x][y] = str(cnt)

        return board