For문을 이용한 풀이

#include <iostream>
#include <cstring>
#include <stack>
#define pii pair<int,int>
#define X first
#define Y second

using namespace std;

int map[2500][2500];
int dx[] {1,-1,0,0};
int dy[] {0,0,-1,1};

//pii searchPoint {0,0};

int areaCnt;
bool endDfs = false;

int main() {
	int t;
	cin >> t;
	
	while (t--) {
		int m, n, k; // 가로, 세로, 배추의 갯수
		cin >> m >> n >> k;

		stack<pii> stk; 
		
		for (int i = 0; i < k; i++){ // 맵 정보갱신
			int x, y; cin >> x >> y;
			map[y][x] = 1; 
			if(i == 0) stk.push(make_pair(x,y)); // 시작점을 넣어준다
		}

		while (!endDfs) { // 검색이 끝나는 조건

			// 스택이 빌 때까지 반복
			while (!stk.empty()){
				pii curPos = stk.top();// 새로운 노드를 스택에서 뽑는다
				stk.pop();
				map[curPos.Y][curPos.X] = -1; // visited 체크를 해준다

				// 4방향을 탐색한다
				for (int i = 0; i < 4; i++) {
					int nx = curPos.X + dx[i];
					int ny = curPos.Y + dy[i];
					
					// 예외처리
					// visited = continue
					// map out = continue
					if (map[ny][nx] == -1) continue;
					if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;

					// 1을 발견하면 stack 에 넣어준다
					if (map[ny][nx] == 1){ stk.push(make_pair(nx, ny)); } 
				}
			}
			// 하나의 영역 끝남
			// 영역 카운트 증가

			areaCnt++;

			// 다음 영역찾기
			// 다음탐색포인트를 찾았으면 빠져나간다 
			
			bool foundPoint = false;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if(map[i][j] == 1){
						stk.push(make_pair(j,i));
						foundPoint = true;
						break;
					}
					if (i == n - 1 && j == m - 1) {endDfs = true;}
				}
				if(foundPoint)break;
			}
			// 하나의 영역 끝
		}
		// 하나의 테스트 케이스 끝남
		// 결과를 출력하고 결과를 초기화
		cout << areaCnt <<'\n';
		areaCnt = 0;
		endDfs = false;

		// 맵 초기화
		memset(map, 0, sizeof(map));
		
	}
	
	return 0;

}

여긴 적혀있지 않지만 for문으로 새로운 시작점을 찾을 때 처음부터 도는 것이 연산에 무리가 갈 것 같아 이전 검색 지점을 저장하여 그 부분부터 검색하는 것으로 했었다.

BFS와 비교

이용하는 자료형이 다를 뿐 논리는 같다.
BFS
먼저 넣어준 것을 뽑아서 다음 노드를 찾는다.
DFS
나중에 넣어준 것을 뽑아서 다음노드를 찾는다.

For 문의 장단점

재귀에 비해 메모리를 적게 쓴다
다만 코드가 길어질 수 있다

재귀를 이용

다른 사람의 풀이를 보며 복습암기해서 작성했다

실수한 부분

dfs에 넣어줄 때 for문의 제한 조건 부분을 실수로 넣어줬다.
for(int i = 0; i < m; i++) 라면 m을 넣어줘서 dfs가 제대로 갱신되지 않았다
또 dfs 매개변수 전달 시 가로세로 인자를 반대로 주는 실수를 했다

#include <iostream>
#include <cstring>
using namespace std;

int dx[] {1, -1, 0, 0};
int dy[] {0, 0, 1, -1};

int map[2500][2500];
bool visited[2500][2500];

int m, n, k, t;

bool dfs(int x, int y) {
	if(visited[y][x]) return false; // dfs 를 돌 때 방문한 노드 반복 X 
	visited[y][x] = true;

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

		if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
			if (map[ny][nx]) dfs(nx, ny);
		}	
	}
	return true;
}


int main() {
	
	cin >> t;
	
	while (t--) {
		cin >> m >> n >> k;
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		
		for (int i = 0; i < k; i++) {
			int x, y; cin >> x >> y;
			map[y][x] = 1;
		}

		int bugCnt = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(!visited[i][j] && map[i][j]){// 방문하지 않았고 배추가 있다면
					dfs(j, i);	// 관련된 것을 모두 방문처리
					bugCnt++;	// 버그가 커버할 영역추가
				}
			}
		}
		cout << bugCnt << '\n';
	}

	return 0;
}

bool dfs(int x, int y) {
	if(visited[y][x]) return false;
    else return true;
}