[SWEA] 1868. 파핑파핑 지뢰찾기(python)

📌문제

💪아이디어

1. 주변 지뢰갯수 세기
   지뢰가 아닌 ‘.’면 그 위치를 기준으로 8방향에 지뢰 개수를 센다.
   주변의 지뢰 갯수가 0 이면 따로 리스트에 넣는다.
   

2. 주변에 지뢰가 없는 곳부터 클릭하기
   1번에서 주변에 지뢰가 없는 곳을 따로 저장해놓았다. 지뢰가 0인부분부터 누르기 시작한다. 0은 연속적으로 주변 지뢰를 보여주기 때문에 0인 부분부터 누르면 최소 클릭수를 얻을 수 있다.
   또 연속적으로 숫자가 보여지는 기능을 구현하기 위해서 주변 지뢰개수가 0이면 queue에 포함해준다.
   

3. 지뢰가 아닌 부분에서 최소클릭 수 뺴주기
   지뢰가 아니고 주변 지뢰의 개수가 0이상인 곳은 연속적으로 숫자를 보여주지 않는다. 한 번씩 다 눌러줘야한다. 그래서 전체 지뢰가 아닌 개수 - 2번에서 누른 클릭수하면 최소 클릭수를 얻을 수 있다.
   

🥂코드

from collections import deque

dir = (-1,0,1)

def chkBomb():
    global left
    zero = []
    for y in range(N):
        for x in range(N):
            if board[y][x] == '*': continue
            left += 1
            cnt = 0
            for i in range(3):
                for j in range(3):
                    ny, nx = y +dir[i], x + dir[j]
                    if ny==y and nx==x: continue
                    if 0 <= ny < N and 0 <= nx < N and board[ny][nx]=='*': 
                        cnt += 1
            cntBoard[y][x] = cnt
            if cnt==0: zero.append((y,x))
    return zero

def click(y,x):
    global left
    queue = deque()
    clicked[y][x] = True
    queue.append((y,x))
    left -= 1

    while queue:
        cury, curx = queue.popleft()
        for i in range(3):
            for j in range(3):
                ny, nx = cury +dir[i], curx + dir[j]
                if ny == cury and nx == curx: continue
                if 0 <= ny < N and 0 <= nx < N and not clicked[ny][nx] and board[ny][nx]=='.':
                    clicked[ny][nx] = True
                    left -= 1
                    if cntBoard[ny][nx] == 0: queue.append((ny,nx))

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    board = [list(input()) for _ in range(N)]
    cntBoard = [['*' if board[i][j] == '*' else 0 for j in range(N)]for i in range(N)]

    left = 0
    zero = chkBomb()
    clicked = [[False for _ in range(N)]for _ in range(N)]
    answer = 0

    for plot in zero:
        y, x = plot
        if not clicked[y][x]:
            click(y,x)
            answer += 1

    answer += left
    print("#{} {}".format(tc,answer))