[백준 1743번] [DFS] 음식물 피하기

Approach

이 문제와 거의 비슷하다. https://viyoung.tistory.com/317?category=884242 

[백준 1012번] [DFS / BFS] 유기농 배추

다만. Component 개수를 물어보는 것이 아니라 component안에 속한 원소 개수의 최대값이므로 이를 dfs 반환값을 통해 구해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;

int n, m, k;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
int visited[101][101];
int v[101][101];
vector<pii> store;

int dfs(int x, int y){
    visited[x][y] = 1;
    int member = 0;
    for(int i = 0; i < 4; i++){
        int dx = x + move_x[i];
        int dy = y + move_y[i];
        if(dx < 0 || dx > n || dy < 0 || dy > m) continue;
        else{
            if(!visited[dx][dy] && v[dx][dy] == 1){
                member += dfs(dx, dy);
            }
        }
    }
    return member + 1;
    

}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(v, 0, sizeof(v));
    cin >> n >> m >> k;

    for(int i = 0; i < k; i++){
        int a, b;
        cin >> a >> b;
        v[a][b] = 1;
        store.push_back(make_pair(a, b));
    }

    int result = 0;
    for(int i = 0; i < k; i++){
        int x = store[i].first;
        int y = store[i].second;
        if(!visited[x][y]){
            result = max(result, dfs(x, y));
        }
    }
    cout << result << "\n";
    return 0;
}