1743 - 음식물피하기 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/1743

풀이전략

1. 가장 큰 음식물의 크기를 구하라는 것은 사실상 쓰래기들의 영역중 가장 큰 영역을 구하라는 문제이다.
2. 따라서 기존에 풀었던 문제들과 똑같이 DFS로 해결하면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M, K;

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

int DFS(int r, int c){
    int ret = 1;
    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];
        if(a[rr][cc] == 1){
            a[rr][cc] = 0;
            ret += DFS(rr,cc);
        }
    }
    
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> M >> K;
    int ta, tb;
    for(int i=1; i<=K; i++){
        cin >> ta >> tb;
        a[ta][tb] = 1;
    }
    int res = 0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(a[i][j] == 1){
                a[i][j] = 0;
                res = max(res, DFS(i,j));
            }
        }
    }
    cout << res <<endl;
    return 0;
}

소감

영역의 크기를 구할때는 위에서 했듯이 ret += DFS(rr,cc) 이런식으로 모든 값들을 더해주면된다.