11123_양 한마리... 양 두마리...

▶ 실버 2 (DFS)

풀이

DFS나 BFS를 이용하여 덩어리 개수를 세면 되는 간단한 문제입니다.

 

2차원 DFS를 구현하고,

2중 for 문을 이용하여 방문하지 않았고, #이라면 DFS를 실행하여 visited 배열을 갱신해줍니다.

 

이런 방식으로 덩어리 개수를 세면 됩니다.

 

그리고 python에서 DFS를 구현할 때는 sys.setrecursionlimit(10**6) 코드를 추가해야한다.

코드

# 11123_양 한마리... 양 두마리...
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    h, w = map(int, input().split())
    garden = [input().split()[0] for _ in range(h)]

    visited = [[False for _ in range(w)] for _ in range(h)]
    x_dir = [1, -1, 0, 0]
    y_dir = [0, 0, 1, -1]

    def DFS(x, y):
        visited[x][y] = True

        for i in range(4):
            nx, ny = x + x_dir[i], y + y_dir[i]
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and garden[nx][ny] == '#':
                DFS(nx, ny)
        return

    ans = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and garden[i][j] == '#':
                DFS(i, j)
                ans += 1

    print(ans)