본인 풀이

DFS로 풀이했다. 반복문 반복자 변수명때문에 쓸데없는데 시간을 허비했다. 테스트케이스로 여러번 입출력이 이루어지는 문제는 지역변수로 풀이하는게 좋을 것 같다.

#include<bits/stdc++.h>
using namespace std;

int T;
int n, m, k;
int ret = 1;
int visited[50][50];
int a[50][50];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= n || nx >= m){
            continue;
        }

        if(a[ny][nx] && visited[ny][nx] == 0){
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> T;

    for (int i = 0; i < T; i++){
        cin >> n >> m >> k;
        ret = 0;


        // k개만큼 배추 심기
        for (int j = 0; j < k; j++){
            // ix, iy는 배추 위치
            int ix, iy;
            cin >> iy >> ix;
            a[iy][ix] = 1;
        }

        for (int j = 0; j < n; j++){
            for (int z = 0; z < m; z++){
                if(visited[j][z] || a[j][z] == 0){
                    continue;
                }
                dfs(j, z);
                ret++;
            }
        }
        cout << ret << "\n";
        fill(&a[0][0], &a[0][0] + 50 * 50, 0);
        fill(&visited[0][0], &visited[0][0] + 50 * 50, 0);
    }

    return 0;
}

모범 답안

로직은 차이가 없지만 코드가 전체적으로 정리되었다.

#include<bits/stdc++.h>
using namespace std;
int t, ret, m, n, k, x ,y, ny, nx;
int a[51][51];
int visited[51][51];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    for (int i = 0; i < 4; i++){
        ny = y + dy[i];
        nx = x + dx[i];

        if(ny < 0 || nx < 0 || ny >= n || nx >= m){
            continue;
        }
        if(a[ny][nx] && visited[ny][nx] == 0){
            dfs(ny, nx);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;

    while(t--){
        fill(&a[0][0], &a[0][0] + 51 * 51, 0);
        fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
        ret = 0;
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++){
            cin >> x >> y;
            a[y][x] = 1;
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(a[i][j] == 1 && !visited[i][j]){
                    dfs(i, j);
                    ret++;
                }
            }
        }
        cout << ret << "\n";
    }

    return 0;
}