[BOJ 1743] 음식물 피하기

 

1743번: 음식물 피하기

 

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다!!

힌트를 통해 직관적으로 BFS를 사용해서 영역의 최댓값을 구하면 되겠다고 생각할 수 있었다!

주어진 입력의 크기도 크지 않고, 특별한 예외 조건이 없어 일반적인 BFS 로직을 사용하여 문제를 해결할 수 있었다!

 

BFS를 구현해야 하므로 큐를 사용해주었다.

예제 입력 1과 힌트에 나온 그림을 비교했을 때 왼쪽 상단이 (1, 1)이기 때문에 좌표가 0부터가 아닌 1부터 시작하기 때문에 좌표 인덱스가 범위를 넘어설 때 continue를 하는 부분만 주의하여 주면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, k; // 세로, 가로, 음식물 쓰레기의 개수
    cin >> n >> m >> k;

    vector<vector<char>> board = vector(n+1, vector<char>(m+1, '.'));
    vector<vector<bool>> visited = vector(n+1, vector<bool>(m+1, false));

    int r, c;
    for (int i = 0; i < k; ++i) {
        cin >> r >> c;
        board[r][c] = '#';
    }

    queue<pair<int, int>> q;
    int cx, cy, nx, ny;
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {-1, 0, 1, 0};

    int ret = 0; // 가장 큰 음식물의 크기
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (board[i][j] == '.') continue;

            // BFS
            q.push({i, j});
            visited[i][j] = true;
            int cnt = 1;

            while (!q.empty()) {
                cx = q.front().first;
                cy = q.front().second;
                q.pop();

                for (int l = 0; l < 4; ++l) {
                    nx = cx + dx[l];
                    ny = cy + dy[l];

                    if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
                    if (board[nx][ny] == '.') continue;
                    if (!visited[nx][ny]) {
                        q.push({nx, ny});
                        visited[nx][ny] = true;
                        cnt ++;
                    }

                }
            }

            if (cnt > ret) ret = cnt;
        }
    }

    cout << ret;

    return 0;
}