[백준] 유기농 배추 (DFS)

DFS 심화 문제로 쉽게 풀 수 있다.

 

백준 1012 유기농 배추

테스트에 사용된 입력값은 아래와 같다.

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

 

워낙 쉬운 문제라 딱히 주의해야 할 점은 없다. 테스트 케이스가 있으므로 케이스마다 결과 값을 저장하는 변수를 0으로 초기화하고 맵을 초기화하면 된다.

 

#include <stdio.h>
#define MAX 50

int Map[MAX][MAX];

void DFS(int x, int y, int maxX, int maxY) {
	// 방문 표시
	Map[y][x] = 0;
	
	// 왼, 오, 위, 아 체크
	int dirX[] = {-1, 1, 0, 0};
	int dirY[] = {0, 0, -1, 1};
	
	// 4방향 체크
	for (int i = 0; i < 4; i++) {
		int nx = x + dirX[i];
		int ny = y + dirY[i];
		
		// 유효성 체크
		if (nx < 0 || nx >= maxX || ny < 0 || ny >= maxY) {
			continue;
		}
		
		// 이동 가능한지 확인
		if (Map[ny][nx] == 1) {
			DFS(nx, ny, maxX, maxY);
		}
	}
}
void initMap (int * C) {
	*C = 0;
	
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			Map[y][x] = 0;
		}
	}
}

int main(void) {
	int T = 0;
	int C = 0;
	int M = 0, N = 0, K = 0;
	
	scanf("%d", &T);
	
	for (int tc = 0; tc < T; tc++) {
		scanf("%d %d %d", &M, &N, &K);
		
		for (int i = 0; i < K; i++) {
			int x = 0;
			int y = 0;
			
			scanf("%d %d", &x, &y);
			
			Map[y][x] = 1;
		}
		
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (Map[y][x] == 1) {
					C++;
					DFS(x, y, M, N);
				}
			}
		}
		
		printf("%d\n", C);
		
		initMap(&C);
	}
	
	return 0;
}

 

결과는 아래와 같다.

 

이렇게만 나오면 ㄱㅅㄱㅅ