[백준] 3184번 양 (python)

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

3184번: 양

 

"우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다." 이 문장을 중심으로 풀어나가면 된다.

 

일반적으로 탐색만 하는 BFS 문제와 달리 이 문제는 마당 안에 있는 양과 늑대의 수를 상황에 따라 줄여주면서 탐색해야 한다. 즉, 탐색하는 과정에서 양과 늑대의 수를 저장하고 마지막에 수가 더 적은 동물을 빼 주어야 한다.

 

해결 방법은 아래와 같다.

 

1. 먼저 입력받은 양과 늑대의 위치 정보를 기반으로 총 몇 마리의 양과 늑대가 있는지 저장해 준다.

 

2. 양의 위치를 중심으로 탐색할 것이기 때문에 양의 위치도 저장해 주었다. (늑대의 위치를 중심으로 해도 괜찮다.)

 

3. 탐색을 시작한다. 탐색 지점이 #인 경우, v인 경우, o인 경우를 각각 나누어서 생각해 주어야 한다. '.'인 경우는 큐에 무조건 추가할 것이기 때문에 따로 생각해주지 않았다.

• 탐색 지점이 v인 경우 늑대이므로 늑대의 수를 +1 해준다. 그리고 해당 지점을 점으로 바꿔준다.
• 탐색 지점이 o인 경우 양이므로 양의 수를 +1 해준다. 그리고 해당 지점을 점으로 바꿔준다.
• #을 제외한 모든 탐색 지점을 큐에 넣어서 다시 상하좌우로 탐색해 준다.

 

4. 마지막으로 세어준 양의 수와 늑대의 수를 비교해서 더 적은 동물을 빼준다.

 

정답 코드

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

r, c = map(int, input().split())
total_v_count = 0
total_o_count = 0
graph = []

for _ in range(r):
    data = list(map(str, input().strip()))
    total_v_count += data.count('v')
    total_o_count += data.count('o')
    graph.append(data)

o_locations = []
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'o':
            o_locations.append([i, j])

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

dq = deque()
visited = [[False] * c for _ in range(r)]

for location in o_locations:
    dq.append(location)
    v_count = 0
    o_count = 1
    
    while dq: 
        x, y = dq.popleft()
        visited[x][y] = True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                visited[nx][ny] = True
                if graph[nx][ny] == '#':
                    continue

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

                elif graph[nx][ny] == 'o':
                    o_count += 1
                    graph[nx][ny] = '.'
                    
                dq.append([nx, ny])
                
    if o_count <= v_count:
        total_o_count -= o_count
    else:
        total_v_count -= v_count
    
print(total_o_count, total_v_count)