백준 알고리즘 11448번 Ga(python)

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 'w'
    cnt = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == '-':
                q.append((Y, X))
                graph[Y][X] = 'w'
                cnt += 1
    return cnt

for _ in range(int(input())):
    N = int(input())
    graph = [list(input()) for _ in range(N)]
    d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
    res = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'w':
                res += bfs(i, j)
    print(res)