백준 알고리즘 11123번 양 한마리... 양 두마리...(python)

기본적인 DFS & BFS 문제이다.

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x):
    graph[y][x] = '.'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < H) and (0 <= X < W) and graph[Y][X] == '#':
            dfs(Y, X)

for _ in range(int(input())):
    H, W = map(int, input().split())
    graph = [list(input()) for _ in range(H)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 0
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                dfs(i, j)
                cnt += 1
    print(cnt)

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '.'
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < H) and (0 <= X < W) and graph[Y][X] == '#':
                q.append((Y, X))
                graph[Y][X] = '.'

for _ in range(int(input())):
    H, W = map(int, input().split())
    graph = [list(input()) for _ in range(H)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 0
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                bfs(i, j)
                cnt += 1
    print(cnt)