[백준] 3187번 양치기 꿍

💡문제접근

• 문제 조건을 잘 정리해보자.

  • 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 많은 경우 늑대의 개체 수는 0, 양의 개체 수는 전부 살아남는다. 그 외의 경우 늑대의 개체 수는 전부 살아남고 양의 개체 수는 0이 된다.

💡코드(메모리 : 34176KB, 시간 : 216ms)

from collections import deque
import sys
input = sys.stdin.readline

R, C = map(int, input().strip().split())

result = [0, 0]  # 양과 늑대의 수
visited = [[False] * C for _ in range(R)]
graph = []
for _ in range(R):
    graph.append(list(input().strip()))

def BFS(a, b):
    global result
    v, k = 0, 0
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        y, x = queue.popleft()

        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= C or ny < 0 or ny >= R:
                continue
            # R × C 영역 내에 존재하면서 울타리 영역으로 둘러싸인 영역에 대해서
            if 0 <= nx < C and 0 <= ny < R and not visited[ny][nx] and graph[ny][nx] != "#":
                visited[ny][nx] = True
                queue.append((ny, nx))
                if graph[ny][nx] == "v":
                    v += 1
                elif graph[ny][nx] == "k":
                    k += 1
    if v >= k:
        result[1] += v
    else:
        result[0] += k

for i in range(R):
    for j in range(C):
        BFS(i, j)
print(*result)

💡소요시간 : 17m