양치기 꿍[백준 3187]

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

from collections import deque
import sys
input = sys.stdin.read
data = input().split("\n")
R, C = map(int, data[0].split())
graph = [list(data[i]) for i in range(1, R+1)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [[False] * C for _ in range(R)]

def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    sheep, wolf = 0, 0  # 현재 영역의 양과 늑대 수

    while queue:
        cx, cy = queue.popleft()
        
        if graph[cx][cy] == 'k':
            sheep += 1
        elif graph[cx][cy] == 'v':
            wolf += 1

        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            
            if 0 <= nx < R and 0 <= ny < C: 
                if not visited[nx][ny] and graph[nx][ny] != '#': 
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    if sheep > wolf:
        return sheep, 0
    else:
        return 0, wolf

total_sheep, total_wolf = 0, 0
for i in range(R):
    for j in range(C):
        if not visited[i][j] and graph[i][j] != '#':  # 울타리가 아니고 방문하지 않은 곳
            s, w = bfs(i, j)
            total_sheep += s
            total_wolf += w

# 결과 출력
print(total_sheep, total_wolf)