백준 3187 양치기 꿍 (파이썬)

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

3187번: 양치기 꿍

1. 주어진 지도를 탐색하면서 울타리가 아니면 bfs에 입력한다

2. 범위 안에 양과 늑대의 수를 카운트하고 양이 늑대보다 많으면 늑대를 0으로 그 외는 양을 0으로 한다

3. 저장한 늑대와 양의 수 출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q.append([x, y])
    c[x][y] = 1
    v_cnt, k_cnt = 0, 0
    while q:
        x, y = q.popleft()
        if a[x][y] == 'v':
            v_cnt += 1
        elif a[x][y] == 'k':
            k_cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if a[nx][ny] != '#' and not c[nx][ny]:
                    c[nx][ny] = 1
                    q.append([nx, ny])

    if v_cnt >= k_cnt:
        k_cnt = 0
    else:
        v_cnt = 0
    return [v_cnt, k_cnt]

m, n = map(int, input().split())
a = [list(input().strip()) for _ in range(m)]
c = [[0]*n for _ in range(m)]
q = deque()

v, k = 0, 0
for i in range(m):
    for j in range(n):
        if a[i][j] != '#' and not c[i][j]:
            v_cnt, k_cnt = bfs(i, j)
            v += v_cnt; k += k_cnt
print(k, v)