Minesweeper

Minesweeper - LeetCode

접근 방법 [필수 작성]

문제 이해

클릭했을때 각 격자값들을 상황에 맞게 변경해주는 문제
클릭하는건 M 아니면 E임
만약 M을 클릭하면 X 로 바꿔야함
만약 E를 클릭하면 B로 바꾸고 인접한 모든 E를 B로 바꿔야함
근데 만약 B가 지뢰랑 한칸내에 인접해있으면, 인접한 지뢰의 갯수만큼 B를 숫자로 바꿈
더이상 공개할 상자가 없을때까지 한 후 보드를 리턴

제한 조건 확인

최대 50x50 보드
r 은 m 과 매칭
c 는 n 과 매칭

아이디어

클릭한게 M인지 E인지 구분
M이면 X로 바꾸고 해당 보드를 리턴
E이면
8방향으로 방문안했던 미공개 박스 탐색
만약 주변 해당 미공개박스가 M이면 M_count 1증가
만약 주변 해당 미공개박스가 M이 아니면, 해당 미공개 박스 큐에 추가
M_count 가 0이면 B로 바꾸고
M_count 가 0이상 자연수면 해당 숫자로 바꿈

시간복잡도

아무리 많아봐야 보드 전체 원소만큼 탐색하고 8방향 탐색하는 것이기 때문에 250088

자료구조

코드 구현 [필수 작성]

from collections import deque

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        m = len(board)
        n = len(board[0])
        r, c = click[0],click[1]
        dr = [0,1,1,1,0,-1,-1,-1]
        dc = [1,1,0,-1,-1,-1,0,1]
        visited = [[False]*n for _ in range(m)]

        q = deque([(r, c)])
        visited[r][c] = True

        def is_valid(r,c):
            if 0 <= r < m and 0 <= c < n:
                return True
            return False
    
        # 클릭한게 M인지 E인지 구분
        # M이면 X로 바꾸고 해당 보드를 리턴
        while q:
            r,c = q.popleft()
            if board[r][c] == "M":
                board[r][c] = "X"
                return board
        # E이면
        #     8방향으로 방문안했던 미공개 박스 탐색
        #         만약 주변 해당 미공개박스가 M이면 M_count 1증가
        #     M_count 가 0이면 B로 바꾸고
        #         8방향 중 유효한 E 들 추가로 큐에 append
        #     M_count 가 0이상 자연수면 해당 숫자로 바꿈
            elif board[r][c] == "E":
                m_count = 0
                for i in range(8):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if is_valid(nr,nc) and board[nr][nc] == "M":
                        m_count += 1
                if m_count == 0:
                    board[r][c] = "B"
                    for i in range(8):
                        nr = r + dr[i]
                        nc = c + dc[i]
                        if is_valid(nr,nc) and visited[nr][nc] == False and board[nr][nc] == "E":
                            q.append((nr,nc))
                            visited[nr][nc] = True
                else:
                    board[r][c] = str(m_count)

        return board

배우게 된 점 [ 필수 X ]

자유 형식

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!