음식물 피하기 (1743번)
- DFS로 풀이
#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int n, m, k;
int cnt = 1;
int map[101][101];
bool check[101][101];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
int dfs(int x, int y){
check[x][y] = true;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx <n && ny >= 0 && ny < m){
if(!check[nx][ny] && map[nx][ny] == 1){
check[nx][ny] = true;
cnt++;
dfs(nx, ny);
}
}
}
return cnt;
}
int main(){
int res = 0;
int ans;
scanf("%d %d %d", &n, &m, &k);
for(int i=0; i<k; i++){
int a, b;
scanf("%d %d", &a, &b);
map[a-1][b-1] = 1;
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!check[i][j] && map[i][j]==1){
res = max(res, dfs(i, j));
cnt = 1;
}
}
}
printf("%d\n", res);
}