🔗 Full Problem 1012

Hanna, a next-generation farmer, has decided to grow organic cabbage in the highlands of Gangwon-do. Since protecting cabbage from pests is important when growing cabbage without using pesticides, Hanna decides to purchase cabbage whiteworms, which are effective at pest control. These worms live near cabbages and protect them by eating pests. In particular, if even a single cabbage whiteworm lives on a cabbage, it can move to an adjacent cabbage, so that cabbage is also protected from pests as well. (Two cabbages are considered adjacent when one is located directly above, below, to the left, or to the right of the other.)

The land where Hanna grows cabbage is uneven, so the cabbages are planted here and there. Since a group of cabbages that are clustered together only needs a single cabbage whiteworm, you can find out how many worms are needed in total by counting how many separate clusters of adjacent cabbages there are.

For example, if the cabbage field is arranged as shown below, at least 5 cabbage whiteworms are needed.

(0 represents land where no cabbage is planted, and 1 represents land where cabbage is planted.)

The first line of input gives the number of test cases $T$. Then, for each test case, the first line gives the width $M(1 ≤ M ≤ 50)$ and height $N(1 ≤ N ≤ 50)$ of the cabbage field, and the number of positions $K(1 ≤ K ≤ 2500)$ where cabbage is planted. The next $K$ lines each give the position of a cabbage, $X(0 ≤ X ≤ M-1)$, $Y(0 ≤ Y ≤ N-1)$.

For each test case, print the minimum number of cabbage whiteworms needed.

• Input

TC
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

• Output

TC
5
1

• Input

TC
1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

• Output

TC
2

A basic algorithm using either DFS (Depth-First Search) or BFS (Breadth-First Search). No extra computation is needed — just apply whichever of the two algorithms you're more comfortable with, and you're done.

A cabbage whiteworm can be placed on a cabbage, and this worm can move from a cabbage to an adjacent cabbage above, below, to the left, or to the right. In other words, the number of worms needed equals the number of regions where cabbages are connected up, down, left, and right.

Based on the example table given in the problem, the planted cabbage areas can be divided into regions as shown below.

As shown in the image above, there are a total of 5 regions, so 5 worms are needed.

Applying DFS proceeds as follows.

1. Check whether cabbage exists in the current region.
   1. If there is no cabbage, skip it.
2. If there is cabbage, check whether this is the first time visiting the current region.
   1. If it has already been explored, skip it.
3. Mark the current region as visited, and increase the worm count by one.
4. Check whether cabbage exists in the adjacent regions above, below, to the left, and to the right.
   1. Up: $(x, y - 1)$
   2. Down: $(x, y + 1)$
   3. Left: $(x - 1, y)$
   4. Right: $(x + 1, y)$
5. Check whether cabbage exists there and whether it's being explored for the first time.
   1. If it has already been explored, skip it.
6. Mark the current region as visited. Since it's the same region, don't increase the worm count.
7. Repeat steps 1 through 7.

The depth in DFS corresponds to the up/down/left/right concept of each region. When comparing up/down/left/right, remember that the $x$ and $y$ values must remain within the bounds of the given field.

This can be diagrammed as shown below. Already-visited regions are shown in green.

Perform the search.

Check whether the position being explored has cabbage and whether it's being visited for the first time. In the case of $(0, 0)$ in the image, it has cabbage and is being visited for the first time, so it matches the condition.

Add a worm and mark it as visited.

Since it's a new region, add one worm. Mark visited regions as visited to prevent duplicate searches.

Explore adjacent regions.

Explore the adjacent regions above, below, to the left, and to the right. Based on $(0, 0)$, these are $(0, 1)$, $(0, -1)$, $(-1, 0)$, and $(1, 0)$. Since region coordinates must be at least 0, the valid regions are $(0, 1)$ and $(1, 0)$.

Mark the adjacent regions as visited.

$(1, 0)$ has also not yet been visited and contains cabbage. Since it's an adjacent region, don't add a worm — just mark it as visited. Repeat the same process for the other adjacent regions.

Repeating this process allows you to compute the number of regions.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1012 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/13/a1012">1012 풀이</a>
 * @since 2021.06.13 Sun 01:30:12
 */
public class Main
{
	// 배추밭의 가로 길이(x)
	private static int M;
	
	// 배추밭의 세로 길이(y)
	private static int N;
	
	// 배추밭
	private static int[][] area;
	
	// 구역 방문 여부
	private static boolean[][] isVisit;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// 케이스 수
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			M = Integer.parseInt(temp[0]);
			
			N = Integer.parseInt(temp[1]);
			
			// 배추 갯수
			int K = Integer.parseInt(temp[2]);
			
			area = new int[M][N];
			
			isVisit = new boolean[M][N];
			
			// 필요한 배추흰지렁이 수
			int bugs = 0;
			
			for (int j = 0; j < K; j++)
			{
				temp = reader.readLine().split(" ");
				
				int x = Integer.parseInt(temp[0]);
				int y = Integer.parseInt(temp[1]);
				
				area[x][y] = 1;
			}
			
			for (int y = 0; y < N; y++)
			{
				for (int x = 0; x < M; x++)
				{
					// 방문하지 않은 구역에 배추가 있을 경우
					if (area[x][y] == 1 && !isVisit[x][y])
					{
						bugs++;
						
						dfs(x, y);
					}
				}
			}
			
			System.out.println(bugs);
		}
		
		reader.close();
	}
	
	/**
	 * 깊이 우선 탐색 알고리즘
	 *
	 * @param x: [int] x좌표
	 * @param y: [int] y좌표
	 */
	private static void dfs(int x, int y)
	{
		// x의 상하좌우 이동
		int[] dx = { 0, 0, -1, 1 };
		
		// y의 상하좌우 이동
		int[] dy = { -1, 1, 0, 0 };
		
		isVisit[x][y] = true;
		
		for (int i = 0; i < 4; i++)
		{
			int xn = x + dx[i];
			int yn = y + dy[i];
			
			// x, y좌표가 구역 내부에 있으며, 방문하지 않은 구역에 배추가 있을 경우
			if ((xn > -1 && xn < M) && (yn > -1 && yn < N) && area[xn][yn] == 1 && !isVisit[xn][yn])
			{
				dfs(xn, yn);
			}
		}
	}
}

• Graph Theory
• Graph Search
• Breadth-First Search
• Depth-First Search