백준: 3184 양

문제

3184번: 양

 

문제 풀이

 한 영역에 양과 늑대가 있을 때, 양의 수가 늑대보다 많다면 양만 남게 된다. 이와 달리 양의 수가 늑대와 같거나 늑대보다 적게 된다면, 양은 모두 잡아먹히고 늑대만 남게 된다. 이때, 각 영역에 양과 늑대의 수를 구하여 반환하는 문제이다. 문제는 앞서 다룬 단지번호붙이기와 같은 로직으로 풀되, 각 영역의 양의 수와 늑대의 수에 따라 BFS 호출 후에 반환되는 값을 달리하면 된다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < r and 0 <= y < c and not visited[x][y] and graph[x][y] != '#'


def bfs(start):
    q = deque([start])
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    wolf, sheep = 0, 0

    while q:
        x, y = q.popleft()
        if graph[x][y] == 'o':
            sheep += 1
        elif graph[x][y] == 'v':
            wolf += 1
        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy
            if visitable(next_x, next_y):
                visited[next_x][next_y] = True
                q.append((next_x, next_y))
    return [0, sheep] if sheep > wolf else [1, wolf]


if __name__ == '__main__':
    r, c = map(int, stdin.readline().split())
    graph = [list(stdin.readline().strip()) for _ in range(r)]
    visited = [[False] * c for _ in range(r)]
    answer = [0, 0]

    for i in range(r):
        for j in range(c):
            if visitable(i, j):
                visited[i][j] = True
                idx, ret = bfs([i, j])
                answer[idx] += ret

    print(*answer)