[파이썬]baekjoon 11123: 양 한마리... 양 두마리...

https://www.acmicpc.net/problem/11123

11123번: 양 한마리... 양 두마리...

---

간단한 bfs문제. dfs로도 풀 수 있지만, 영역을 구하는 문제는 bfs가 편한거 같아서 bfs로 풀었다.

 

#가 상하좌우로 밀집해 있다면, 하나의 군집으로 체크!

def bfs(start):
    q = []
    q.append(start)
    arr[y][x] = "."
    directy = [-1, 1, 0, 0]
    directx = [0, 0, -1, 1]
    while q:
        nowy, nowx = q.pop(0)

        for i in range(4):
            dy = directy[i] + nowy
            dx = directx[i] + nowx

            if 0<=dy<H and 0<=dx<W :
                if arr[dy][dx] ==".": continue
                if arr[dy][dx] =="#":
                    q.append((dy,dx))
                    arr[dy][dx] = "."


t = int(input())
for tc in range(t):
    H,W = list(map(int,input().split()))
    arr=[list(input()) for _ in range(H)]
    answer = 0
    for y in range(H):
        for x in range(W):
            if arr[y][x] =="#":
                arr[y][x] = "."
                bfs((y,x))
                answer += 1
    print(answer)