[Baekjoon] 1012번: 유기농 배추

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

1012번: 유기농 배추

 

---

 

문제 해결 과정

착안

상하좌우로 연결된 배추들 사이에는 하나의 배추흰지렁이만 있어도 해충 예방이 가능하므로, 이를 표현하기 위해 편의상  아래와 같은 과정을 주어지는 배추밭 모양에 따라 반복적으로 수행하여 필요한 총 배추흰지렁이의 수를 계산한다.

 

• 배추가 심어진 땅이 발견되면 필요한 배추흰지렁이의 수를 1만큼 증가시킨다.
• 깊이 우선 탐색(depth-first search, DFS) 또는 너비 우선 탐색(breadth-first search, BFS)의 방법에 따라, 현재 위치에서 시작하여 배추흰지렁이가 이동 가능한 경로 내에 존재하는 모든 배추가 심어진 땅을 찾아 값을 0으로 변경시킨다(재계산하지 않도록).

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int T, M, N, K;

void Expansion(int field[50][50], int x, int y)
{
	field[y][x] = 0;

	if (x - 1 >= 0 && field[y][x - 1])
		Expansion(field, x - 1, y);

	if (x + 1 < M && field[y][x + 1])
		Expansion(field, x + 1, y);

	if (y - 1 >= 0 && field[y - 1][x])
		Expansion(field, x, y - 1);

	if (y + 1 < N && field[y + 1][x])
		Expansion(field, x, y + 1);

}

int main()
{
	cin >> T;

	while (T--)
	{
		cin >> M >> N >> K;

		int worms = 0;
		int field[50][50] = { 0, };

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

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (field[i][j])
				{
					Expansion(field, j, i);
					worms++;
				}

		cout << worms << "\n";
	}

	return 0;
}

 

실행 결과