1012 - 유기농배추 - DFS

문제

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

풀이전략

1. 이것도 이전에 풀었던 단지구하기와 같은 문제이다. 이름만 영토에서 지렁이로 바뀐 것 뿐이다.
2. 마찬가지로 dx, dy를 만들어서 이동한다.
3. M, N 은 50이하이므로 시간과 공간은 충분하다.

코드

#include<bits/stdc++.h>

using namespace std;

int M, N, K, T;
int mp[52][52];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
void DFS(int r, int c){
    for(int i=0; i<4; i++){
        int rr = r + dy[i];
        int cc = c + dx[i];

        if(mp[rr][cc] == 1){
            mp[rr][cc] = 0;
            DFS(rr,cc);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> T;
    for(int t =0; t<T; t++){
        memset(mp, 0, sizeof(mp));
        cin >> M >> N >> K;
        int ta, tb;
        for(int i=1; i<=K; i++){
            cin >>ta >> tb;
            //// 0도 들어오니 나는 1부터 시작하고 싶기때문에 이렇게 체크해줘야함.
            //// 실수 2 : x가 먼저들어오는지, y가 먼저들어오는지 제대로확인하기.
            mp[tb+1][ta+1] = 1;
        }
        int cnt = 0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                
                if(mp[i][j] == 1){
                    
                    mp[i][j] = 0;
                    DFS(i, j);
                    cnt++;
                }
            }
        }
        cout<<cnt<< endl;
    }
    
    return 0;
}

소감

문제는 쉬웠으나 또 문제를 제대로 읽지 않았다. 나는 항상 배열을 1부터 시작하는데 이 문제에서는 0에서부터 input이 들어오므로 +1 을 해주는것을 잊지말아야한다. 또한 문제에서 x가 먼저들어오는지 y가 먼저들어오는지 확인해야한다.