유기농 배추

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

1012번: 유기농 배추

 

특정 배추를 선택할 때 인접 배추들도 검색을 해야한다.

쉽게 생각하면 지뢰찾기에서 연쇄처리와 같다고 볼 수 있다.

Queue에 현재 위치를 넣고 계속해서 주변에 만족하는 배추들의 위치를 추가한다.

이런식으로 모든 배추를 검색하면 DFS가 된다.

또 다른 예로는 퍼즐버블게임이나 뿌요뿌요같은 퍼즐게임에서 연쇄처리를 할 때 사용할 수 있겠다.

using namespace std;

bool MAP[50][50];
typedef struct{ int x, y; }pos;
int main()
{
	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		memset(MAP, 0, sizeof(MAP));
		int M, N, K;
		scanf("%d %d %d", &M, &N, &K);

		for (int i = 0; i < K; i++)
		{
			int X, Y;
			scanf("%d %d", &X, &Y);
			MAP[Y][X] = 1;
		}

		int num = 0;
		for (int i = 0; i < N;i++)
		for (int j = 0; j < M; j++)
			if (MAP[i][j])
			{
				vector stack;
				pos temp;
				temp.x = j; temp.y = i;
				stack.push_back(temp);
				++num;
				while (stack.size()>0)
				{
					pos t = stack.back();
					stack.pop_back();
					MAP[t.y][t.x] = 0;
					if (t.x - 1 >= 0)
					{
						pos tt;
						tt.x = t.x - 1; tt.y = t.y;
						if (MAP[tt.y][tt.x])
							stack.push_back(tt);
					}
					if (t.y + 1 < N)
					{
						pos tt;
						tt.x = t.x; tt.y = t.y + 1;
						if (MAP[tt.y][tt.x])
							stack.push_back(tt);
					}
					if (t.y - 1 >= 0)
					{
						pos tt;
						tt.x = t.x; tt.y = t.y - 1;
						if (MAP[tt.y][tt.x])
							stack.push_back(tt);
					}
					if (t.x + 1 < M)
					{
						pos tt;
						tt.x = t.x + 1; tt.y = t.y;
						if (MAP[tt.y][tt.x])
							stack.push_back(tt);
					}
				}
			}
			printf("%d\n", num);
	}
	return 0;
}