주어진 맵을 탐색하며 연결된 컴포넌트의 개수를 찾는 문제이다.
DFS여러번 갈겨주면 된다.

1. 풀이

#include <bits/stdc++.h>
const int max_y=54;
const int max_x=54;
int a[max_y][max_x];
int visited[max_y][max_x];
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
int ret,m,n,ny,nx;

using namespace std;

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]==0) continue;
        if(visited[ny][nx]) continue;
        DFS(ny,nx);
    }
    
}

int main() {
    int T, k, tmp_y, tmp_x;
    cin >> T;
    while(T--) {
        ret = 0;
        fill(&a[0][0],&a[0][0]+max_y*max_x,0);
        fill(&visited[0][0],&visited[0][0]+max_x*max_y, 0);
        cin >> m >> n >> k;
        while(k--) {
           cin >> tmp_x >> tmp_y;
           a[tmp_y][tmp_x]=1;
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(visited[i][j]==0 && a[i][j]==1) {
                    DFS(i,j); 
                    ret++;
                }
            }
        }
        cout << ret << "\n";
    }
    return 0;
}

main() 내부에서 DFS 호출전에 꼭!! if문으로 if(visited[i][j]==0 && a[i][j]==1)와 같이 방문 여부, 맵 상으로 1 여부 를 확인해줘야한다.

2. 오답 노트

(1) 2차원 배열의 초기화

2차원 배열을 초기화하는 것은 놓치지 않았으나, 2차원 배열의 주소 받아오는 문법에 미숙하여 틀렸다.

✍ 1차원 배열의 경우는

fill(arr+0,arr+arr+배열의 크기,초기화 값)

이런식으로 사용한다

✍ 2차원 배열의 경우는

fill(&arr[0][0]+0,&arr[0][0]+배열의 크기,초기화 값)

EX)  fill(&a[0][0],&a[0][0]+max_y*max_x,0);

이런식으로 사용한다