[DP] 백준 - 양 3154번

양 3154번

😒 문제 요약

양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

👏 key point

전형적인 dfs,bfs 문제이다. 한 울타리 내에서 양의 개수와 늑대의 개수를 구한 후 양의 개수가 더 많으면 양의 수를 , 그렇지 않을 경우 늑대의 수 구하여 더하는 식으로 풀면 쉽게 풀 수 있는 문제이다.

from collections import deque
# n = 세로, m = 가로
n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(str,input())))

visited = [[False]*m for _ in range(n)]

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

sheep = 0
wolf = 0

def bfs(a,b):
    q = deque()
    result = [0,0]  # 울타리 내에 있는 양,늑대의 마리 수 정보를 넣은 리스트

    #처음 방문했을 때 양 또는 늑대가 있을 때
    if graph[a][b] == 'o':
        result[0] += 1
            
    elif graph[a][b] == 'v':
        result[1] += 1

    q.append((a,b))
    visited[a][b] = True
   
    while q:
        y,x = q.popleft()
       
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= m or ny >= n:
                continue

            if graph[ny][nx] != '#' and visited[ny][nx] == False:
                visited[ny][nx] = True

                #이동 시 양 또는 늑대가 있을 시 
                if graph[ny][nx] == 'o':
                    result[0] += 1

                elif graph[ny][nx] == 'v':
                    result[1] += 1

                q.append((ny,nx))
           
    return result    
                            

for i in range(n):
    for j in range(m):
        if graph[i][j] != '#' and visited[i][j] == False:
            
            ans = bfs(i,j)
            
            #전체 양과 늑대의 개수 sheep, wolf 
            if ans[0] > ans[1]:
                sheep += ans[0]

            else:
                wolf += ans[1]
      
print(sheep,end = " ")
print(wolf)