백준 1012: 유기농 배추

문제 요약

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

각 배추의 위치 정보와 방문 여부를 2차원 배열로 선언하고, (0,0) 부터 (n - 1,m - 1)까지 순회하며 map[i][j]에 배추가 있을경우 DFS하면 된다.

DFS에서는 i와 j값에 따라 적절하게 함수를 재귀적으로 호출하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

bool visited[50][50];
int map[50][50];
int m, n;

void dfs(int i, int j) {
	visited[i][j] = true;
	if (i < n - 1)
		if (map[i + 1][j] && !visited[i + 1][j]) dfs(i + 1, j);
	if (i > 0)
		if (map[i - 1][j] && !visited[i - 1][j]) dfs(i - 1, j);
	if (j < m - 1)
		if (map[i][j + 1] && !visited[i][j + 1]) dfs(i, j + 1);
	if (j > 0)
		if (map[i][j - 1] && !visited[i][j - 1]) dfs(i, j - 1);
}

int main()
{
	int cnt, k, t, in1, in2;
	cin >> t;
	while (t--) {
		cnt = 0;
		scanf("%d%d", &m, &n);
		scanf("%d", &k);
		for (int i = 0; i < 50; i++) {
			for (int j = 0; j < 50; j++) {
				map[i][j] = 0;
				visited[i][j] = false;
			}
		}
		for (int i = 0; i < k; i++) {
			scanf("%d%d", &in1, &in2);
			map[in2][in1] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j]) {
					if (map[i][j]) {
						dfs(i, j);
						cnt++;
					}
					else visited[i][j] = true;
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}