[swea 1868-파이썬] 파핑파핑 지뢰찾기

사용언어 : PYTHON

풀이

1. 행 우선 방향으로 탐색을 진행하다 0인 곳을 만나면 BFS를 수행(연쇄적으로 클릭)하며 정답(ans)를 1증가 

 

이때 0으로 인해 연쇄적으로 클릭된 곳을 -로 표시

 

2. 행 우선 방향으로 다시 탐색하며 연쇄적으로 클릭되지 않은 곳의 갯수만큼 정답(ans)에 추가  

 

 

 

코드

import sys
from collections import deque
input = sys.stdin.readline

# SWEA 파핑파핑 지뢰찾기

# 1. 전체를 탐색하다 0을 만나면 BFS 수행 (방문체크), cnt += 1
# 2. 체크 되지 않은 칸 세기



def click(r, c): # 클릭을 수행하고(중복 클릭은 수행하지 않음), 0이면 True를 리턴하는 함수

    if arr[r][c] == '*' or arr[r][c]=='-':
        return False

    if chk[r][c]: # 클릭했던 곳은 다시 클릭하지 않음, chk[r][c]가 true였으면 이미 BFS수행 했을 것임(행 우선으로 click을 수행하기 때문)
        return False

    chk[r][c]=True

    cnt = 0

    for d in range(8):
        nr = r + dr[d]
        nc = c + dc[d]
        if nr < 0 or nr >= N: continue
        if nc < 0 or nc >= N: continue
        if arr[nr][nc]=='*':
            cnt+=1

    # arr[r][c]=cnt # 방문체크는 visited에서 수행하고 연쇄 폭발은 -로 표시하기 때문에 클릭한 곳의 숫자 표시는 불필요함

    if cnt==0:
        return True

    return False

def bfs(r,c): # 연쇄 클릭을 수행하고 '-' 표시

    queue = deque()

    queue.append([r,c])
    arr[r][c] = '-'

    while queue:
        row,col = queue.popleft()

        for d in range(8):
            nr = row + dr[d]
            nc = col + dc[d]
            if nr<0 or nr>=N : continue
            if nc<0 or nc>=N : continue
            if click(nr,nc):
                queue.append([nr,nc])
            arr[nr][nc] = '-' # 0으로 인해서 연쇄적으로 터진 곳을 '-'로 표시



T = int(input())

for t in range(1, T + 1):
    N = int(input())
    arr = [list(input().strip()) for _ in range(N)]
    chk = [[False] * N for _ in range(N)]
    ans = 0

    for i in range(N): # 전체를 탐색하며 0이면 bfs수행
        for j in range(N):
            if click(i, j):  # 클릭 했는데 0이면
                bfs(i, j)
                ans+=1



    for i in range(N): # 연쇄클릭이 일어나지 않은곳의 갯수를 카운트 
        for j in range(N):
            if arr[i][j]!='-' and arr[i][j]!='*': # arr[i][j]=='.'로 해도 됨
                ans+=1


    print('#{} {}'.format(t,ans))