[BOJ][1012] 유기농 배추

소스 코드

---

#include <iostream>
#include <queue>
#include <cstring>
#define endl "\n"
using namespace std;

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

int T; // 테스트 케이스 개수
int M; // 배추밭 가로 길이
int N; // 배추밭 세로 길이
int K; // 심어진 배추 개수
int map[50][50]; // 배추밭 배추 존재 여부

int map_init[50][50]; // 배추밭 초기화용

void input()
{
	cin >> M >> N >> K;

	memcpy(map, map_init, sizeof(map_init));

	for (int i = 0; i < K; ++i)
	{
		int x, y;
		cin >> x >> y;
		map[y][x] = 1;
	}
}

void solve()
{
	int cnt = 0;

	int visited[50][50] = { 0, };

	for (int r = 0; r < N; ++r)
	{
		for (int c = 0; c < M; ++c)
		{
			if (visited[r][c]) continue;
			if (map[r][c] == 0) continue;

			visited[r][c] = 1;
			queue<pair<int, int> > q;
			q.emplace(r, c);

			while (!q.empty())
			{
				auto cur = q.front(); q.pop();
				int cur_r = cur.first;
				int cur_c = cur.second;

				for (int dir = 0; dir < 4; ++dir)
				{
					int n_r = cur_r + dy[dir];
					int n_c = cur_c + dx[dir];

					if (n_r < 0 || n_r >= N || n_c < 0 || n_c >= M) continue;

					if (map[n_r][n_c] == 0) continue;
					if (visited[n_r][n_c]) continue;

					visited[n_r][n_c] = 1;
					q.emplace(n_r, n_c);
				}
			}

			++cnt;
		}
	}

	cout << cnt << endl;
}

int main()
{
	freopen("boj_1012.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		input();
		solve();
	}

	return 0;
}

해설

---

영역의 개수를 구하는 대표적인 BFS 문제

의사 코드

---

1. 배추의 위치가 하나씩 주어지므로 이를 배추밭에 반영해야 한다. 단, 미리 배추밭을 초기화 하지 않으면, 이전 테스트 케이스가 정답에 영향을 줄 수 있다. 미리 초기화해야 하는 부분은 정리해 놨다가 매 테스트케이스마다 초기화 할 수 있도록 하자.
2. 배추밭의 각 위치마다 BFS 탐색을 시작할지 말지 결정
   2-1. 만약 해당 위치에 이미 방문한 적이 있다면 패스.
   2-2. 만약 해당 위치에 배추가 없다면 패스.
   2-3. 위 두 조건에 해당하지 않으면 해당 위치 방문처리 및 큐에 해당 위치 삽입 후 BFS 탐색으로 인접한 배추의 위치 방문처리 + 결과값 1 증가.
3. 결과값 출력

BFS 탐색

---

1. 큐가 비어 있지 않다면 아래 과정 반복
2. 큐의 front pop => 현재 위치
3. 현재 위치의 상, 하, 좌, 우 4방향 탐색
   3-1. 해당 방향으로의 다음 위치가 배추밭 영역을 벗어난 경우 패스.
   3-2. 해당 방향으로의 다음 위치에 배추가 없을 경우 패스.
   3-3. 해당 방향으로의 다음 위치에 배추가 있지만 방문한 경우 패스.
   3-4. 해당 방향으로의 다음 위치가 위 세 조건에 해당하지 않으면 방문처리 및 큐에 삽입.