[백준] 1012 유기농 배추

문제출처] https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

문제요약

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

배추가 심어진 밭은 '1', 아무것도 안심어진 밭은 '0'으로 표기했을 때, 배추가 심어진 박스의 개수를 구하는 문제

풀이

탐색 알고리즘을 이용하여 문제풀이를 할 수 있습니다. 2차원 배열을 탐색해야 되므로 다음 행과 열을 가리키기 위해 nx[]와 ny[]를 전역 변수로 선언해 주었습니다.  search()함수에서 매개변수로 현재 행과 열, 그리고 배추밭의 가로, 세로 사이즈를 받아 탐색을 합니다. 방문한 배열의 경우 2차원 배열 visited 를 1로 초기화 해주어 방문처리를 해줍니다. 

메인 함수에서 모든 배추밭을 순회하면서 배추가 심어진 블럭의 개수를 cnt를 통해서 카운트 해줍니다.

소스코드는 C/C++로 작성하였습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int field[51][51];
int visited[51][51];
int cnt;
int nx[] = { 0,0,-1,1 };
int ny[] = { -1,1,0,0 };

void search(int row, int col, int m, int n) {
	visited[row][col] = 1;

	for (int i = 0; i < 4; i++) {
		int nextrow = row + nx[i];
		int nextcol = col + ny[i];
		if (nextrow <0 || nextcol<0 || nextrow>m || nextcol>n) 
        	continue;
		else {
			if (field[nextrow][nextcol] == 1 && visited[nextrow][nextcol] == 0)
           			search(nextrow, nextcol, m,n);    
		}
	}
}


int main() {
	int casenum;
	cin >> casenum;

	for (int i = 0; i < casenum; i++) {
		int m, n, k;
		cin >> m >> n >> k;
		for (int j = 0; j < k; j++) {
			int x, y;
			cin >> x >> y;
			field[x][y] = 1;
		}
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < n; b++) {
				if (field[a][b] == 1 && visited[a][b] == 0) {
					search(a, b, m,n);
					cnt++;
				}
			}
		}

		for (int a = 0; a < 51; a ++) {
			for (int b = 0; b < 51; b++) {
				field[a][b] = visited[a][b] = 0;
			}
		}
		cout << cnt << endl;
		cnt = 0;
	}
}