[1743] 음식물 피하기

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

1743번: 음식물 피하기

<문제>

음식물의 좌표에 따라 맵을 채워주고, 4방향 bfs를 이용해 영역의 넓이를 구해준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, k, a[101][101], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
bool visited[101][101];
int f(int sy, int sx) {
    visited[sy][sx] = true;
    queue<pair<int, int>> q;
    q.push({sy, sx});
    int cnt = 1;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 1 || x < 1 || y > n || x > m) continue;
            if (a[y][x] == 1 && !visited[y][x]) {
                visited[y][x] = true;
                cnt++;
                q.push({y, x});
            }
        }
    }
    return cnt;
}
int main(void) {
    cin >> n >> m >> k;
    int i, j;
    for (i = 0; i < k; i++) {
        int y, x;
        cin >> y >> x;
        a[y][x] = 1;
    }
    int ans = 0;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (a[i][j] == 1 && !visited[i][j]) {
                int ret = f(i, j);
                ans = max(ret, ans);
            }
        }
    }
    cout << ans;
    return 0;
}