BOJ - 3184

백준 문제 링크
양

❓접근법

1. BFS를 사용했다.
2. wolf와 sheep 변수를 만들어 울타리 안의 각각 마리 수를 구한다.
3. 방문한 '.'(빈 필드)은 '#'(울타리)으로 만들어준다.
4. 울타리 안의 양과 늑대의 수를 비교했을 때,
   늑대가 양보다 많으면 (0, wolf) 반환
   양이 늑대보다 많으면 (sheep, 0)반환 해준다.
5. 모든 영역에서 탐색한 결과를 ans_sheep, ans_wolf에 더해서 반환하면 된다.

👌🏻코드

N,M = map(int, input().split())

lst = []

for _ in range(N):
    lst.append(list(input()))
        
from collections import deque

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

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    
    wolf = sheep = 0
    
    if lst[x][y] == 'v':
            wolf += 1
    if lst[x][y] == 'o':
            sheep += 1
    
    lst[x][y] = '#'
    
    
    while queue:
        x,y = queue.popleft()
        
        
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0 <= nx < N) and (0 <= ny < M) and (lst[nx][ny] != '#'):
                
                
                if lst[nx][ny] == 'v':
                    wolf += 1
                elif lst[nx][ny] == 'o':
                    sheep += 1
                    
                    
                queue.append((nx,ny))
                lst[nx][ny] = '#'
                
    
    if wolf >= sheep:
        return 0, wolf
    elif sheep > wolf:
        return sheep, 0
    
    
ans_sheep = 0
ans_wolf = 0

for i in range(N):
    for j in range(M):
        if lst[i][j] in 'ov':
            count_sheep, count_wolf = bfs(i,j)
            ans_sheep += count_sheep
            ans_wolf += count_wolf
            
print(ans_sheep, ans_wolf)