(백준/C++) 1743-음식물 피하기

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

문제 해석(시간 제한 2초)

(N * M)배열에서 음식물이 떨어져 있는 공간이 있고 음식물들은 근처에 있는 것끼리 뭉쳐 큰 음식물 쓰레기가 된다고 합니다. 여기서 움직이는 이는 '제일 큰 음식물만'은 피해 가려고 합니다. 여기서 가장 큰 음식물의 크기를 구하는 것이 이 문제의 목표입니다.

여기서 '제일 큰 음식물'이란 자기가 속한 칸을 기준으로 +1, -1칸 범위에 가로-세로 칸이 범위입니다. 즉 범위 안에 음식물이 있다면 음식물은 서로 뭉치게 됩니다.

시간제한 2초이고 N(1<= N <= 100), M(1 <= M <= 100)이므로 O(NM)==O(100*100)이므로 DFS/BFS를 이용해서 여유롭게 풀 수 있습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int row, col, k;
int map[101][101];
int visit[101][101];
int garbage = 0 ,cnt = 0;

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int r, int c) {
    visit[r][c] = true;
    cnt += 1;
    garbage = max(cnt, garbage);

    for(int i = 0; i < 4; i++) {
        int ny = r + dy[i];
        int nx = c + dx[i];
        if(r <= 0 || c <= 0 || r > 100 || c > 100) return;
        if(!visit[ny][nx] && map[ny][nx] == 1) {
            dfs(ny, nx);
            
        }
    }
}

int main() {
    cin >> row >> col >> k;
    for(int i = 0; i < k; i++) {
        int y, x;
        cin >> y >> x;
        map[y][x] = 1;
    }
    for(int i = 1; i <= row; i++) {
        for(int j = 1; j <= col; j++) {
            if(map[i][j] == 1 && !visit[i][j]) {
                cnt = 0;
                dfs(i, j);
            }
        }
    }
    cout << garbage << endl;
    return 0;
}