BOJ 3184 · 양

알고리즘 분류 : BFS  

남아있는 양과 늑대의 수를 구하는 문제다. 특정 지역에서 양이 늑대보다 많으면 양만 살아남고, 그렇지 않으면 늑대만 살아남는다.

• 각 영역은 울타리('#')로 둘러싸여 있으며, 영역 내부는 BFS를 통해 탐색한다.
• BFS 탐색을 하면서 양('o')의 수와 늑대('v')의 수를 센다.
• 양이 늑대보다 많으면, 양만 살아남으므로 총 양의 수에 더한다.
• 늑대가 양보다 많거나 같으면, 늑대만 살아남으므로 총 늑대의 수에 더한다.
• 위의 과정을 모든 영역의 탐색이 끝날 때까지 진행한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int r, c, sheep, wolf;
char a[251][251];
bool check[251][251];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

void bfs(int i, int j) {
    queue<pair<int, int>> q;
    q.push(make_pair(i, j));
    check[i][j] = true;
    int o = 0, v = 0;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        if (a[x][y] == 'o') o++;
        if (a[x][y] == 'v') v++;
        for (int k=0; k<4; k++) {
            int nx = x+dx[k], ny = y+dy[k];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (check[nx][ny] || a[nx][ny] == '#') continue;
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
        }
    }
    if (o > v) sheep += o;
    else wolf += v;
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i=0; i<r; i++) scanf("%s", a[i]);
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            if (!check[i][j] && a[i][j] != '#') {
                bfs(i, j);
            }
        }
    }
    printf("%d %d\n", sheep, wolf);
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs(i, j):
    global sheep, wolf
    q = deque()
    q.append((i, j))
    check[i][j] = True
    o, v = 0, 0
    while q:
        x, y = q.popleft()
        if a[x][y] == 'o':
            o += 1
        if a[x][y] == 'v':
            v += 1
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                continue
            if not check[nx][ny] and a[nx][ny] != '#':
                q.append((nx, ny))
                check[nx][ny] = True
    if o > v:
        sheep += o
    else:
        wolf += v

r, c = map(int, input().split())
a = [list(input().strip()) for _ in range(r)]
check = [[False]*c for _ in range(r)]
sheep, wolf = 0, 0
for i in range(r):
    for j in range(c):
        if not check[i][j] and a[i][j] != '#':
            bfs(i, j)
print("%d %d" % (sheep, wolf))

---

참고

• 백준 온라인 저지 : BOJ 3184