[백준 1012] 유기농 배추

 

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

#include <stdio.h>
int T;
int M, N, K;
int cabbage[50 + 10][50 + 10];
int bug_cnt;

int dir_x[4] = { 0, 0, 1, -1 };  // 방향벡터
int dir_y[4] = { 1, -1, 0, 0 };	 // 어차피 상하좌우 스캔이므로 순서 중요하지 않음

void init(void)		// 테스트케이스가 여러개 이므로 초기화
{
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cabbage[i][j] = 0;
		}
	}
	M = N = K = 0;
	bug_cnt = 0;
}


void get_bug(int x, int y)		//재귀함수
{
	cabbage[x][y] = 2;
	int nx, ny;
	for (int p = 0; p < 4; p++) {
		nx = x + dir_x[p];
		ny = y + dir_y[p];
		if (cabbage[nx][ny] == 1) { // 아직 방문하지 않은 배추가 있다면 방문
			get_bug(nx, ny);
		}
	}
	return;
}


void search(void)		// 배추 밭을 scan하는 함수
{
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (cabbage[i][j] == 1) {	// 배추가 있을 때만 재귀 호출
				get_bug(i, j);
				bug_cnt++;	// 재귀함수 탈출하면 무조건 bug_cnt += 1 해준다
			}
		}
	}
}


int main(void)
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d %d", &M, &N, &K);
		int u = 0; int v = 0;
		for (int j = 0; j < K; j++) {
			scanf("%d %d", &u, &v);
			cabbage[u][v] = 1;
		}
		search();
		printf("%d\n", bug_cnt);
		init();
	}
	return 0;
}

 

// init 함수

일단 주의해야할 점은 "테스트케이스가 여러개"라는 점이다. 

따라서 하나의 테케가 끝나면 T변수를 제외하고는 모두 처음의 상태로 초기화해줘야 한다. 

이러한 이유 때문에 init() 함수를 따로 생성하여 초기화를 담당해주도록 했다.  

 

// search 함수

지렁이가 필요한지를 확인하기 위해 배추밭을 스캔해야 한다. 

매번마다 재귀함수 호출하기 싫어서 cabbage[i][j] == 1일 때, 즉 배추가 발견되었을 때만 get_bug함수를 호출하도록 조건문을 걸어주었다. 

그리고 재귀함수를 탈출하여 다시 search함수로 돌아오면, 주변의 배추가 있는지 없는지를 모두 확인하고 온 것이기 때문에 bug_cnt를 1개 추가해준다. 

 

 

// get_bug 함수

이때 받는 파라미터는 search 함수에서 이미 배추가 있다고 확인한 좌표이다. 

따라서 cabbage[x][y] = 2로 바꾸어 방문처리 해줌으로써, 다음 스캔때 해당 좌표를 다시 확인하는 것을 방지한다. 

또한 상, 하, 좌, 우에 배추가 있는지 없는지를 판단하기 위해, 새로운 변수 nx, ny를 두고 방향벡터의 인덱스(p)를 옮겨주면서 확인한다. 그러다가 cabbage[nx][ny] = 1이면 인접한 새로운 좌표에도 배추가 있다는 것이므로, get_bug를 재귀호출 한다. 인접한 모든 1에 방문하면서 2로 방문처리하는 과정을 반복한다.