이번 문제는 깊이우선탐색을 통해 해결하였다. 4가지 이동 방향을 따로 관리하여 모든 방향으로의 경우에 대해서 재귀호출을 통해 그리드에 #를 없애는 과정을 반복하고 재귀함수를 처음 호출할 때에 카운팅 변수를 증가시켜주며 카운팅을 하였다. 다른 깊이우선탐색 문제와 유사한 문제였다. 재귀 에러가 발생하여서 sys.setrecursionlimit(10**9)를 사용해주었다.

• 재귀 제한을 늘린다.
• dfs 함수를 y, x를 인자로 갖도록 선언한다.
  -> grid[y][x]를 '.'으로 갱신한다.
  -> 4가지 방향에 대한 정보를 저장할 리스트 dy, dx를 선언하고 4가지 방향을 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 선언한다.
  --> nx를 x+dx[i]로 선언한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 h보다 작고, nx가 w보다 작고, grid[ny][nx]가 '#'일 경우 dfs(ny, nx)를 재귀호출한다.
• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> h, w를 입력받는다.
  -> 그리드를 저장할 리스트 grid를 선언한다.
  -> 카운팅 변수로 이용할 변수 cnt를 0으로 선언한다.
  -> h번 반복하는 for문을 돌린다.
  --> grid를 입력받는다.
  -> h번 반복하는 i에 대한 for문을 돌린다.
  --> w번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 grid[i][j]가 '#'일 경우,
  ----> dfs(i, j)를 호출한다.
  ----> cnt를 1 증가시킨다.
  -> cnt를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x):
    grid[y][x]='.'
    dy=[0, 0, -1, 1]
    dx=[-1, 1, 0, 0]
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<h and nx<w and grid[ny][nx]=='#':
            dfs(ny, nx)
t=int(input())
for _ in range(t):
    h, w=map(int, input().split())
    grid=[]
    cnt=0
    for _ in range(h):
        grid.append(list(str(input())))
    for i in range(h):
        for j in range(w):
            if grid[i][j]=='#':
                dfs(i, j)
                cnt+=1
    print(cnt)