[백준] 1012번: 유기농 배추

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

1012번: 유기농 배추

배추밭을 밭의 세로 가로 길이를 저장할 변수는 전역변수로 해서 각 함수에서 자유롭게 접근할 수 있도록 했다. 

 

main()

에서는 입력을 받고, for문을 통해 배추밭별로 worms()라는 필요한 배추벌레의 수를 계산하는 함수를 호출하도록 했다. - worms()와 dfs()를 호출할 때 parameter을 줄이기 위해

 

worms()

는 dfs()를 호출해서, 배추밭에 몇 개의 덩이(배추벌레 1마리가 처리할 수 있는 밭 덩이)가 있는지를 계산해서 return한다. 

 

dfs()

는 주이진 정점의 동서남북을 탐색해, 이 중 배추가 심어져있는 밭이면 여기에 대해 다시 dfs를 호출하게 함으로써 depth first search가 일어나게 한다. 

 

* 처음에 graph를 전역변수로 해주려고 했는데, 각 배추밭의 모든 정점을 0으로 초기화한 다음, 세 번째 라인부터 들어오는 배추가 심겨진 위치를 graph에 표시하게 하려고 그냥 worms()의 지역변수로 만들어주고, dfs()에 parameter로 그 주소값을 넘겨줬다. 

 

// 1012

#include <iostream>
#include <vector>

using namespace std;

//int graph[50][50];
int m, n;

void dfs(int x, int y, int graph[50][50]){
	
	graph[x][y] = 0;
	// direction vector
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, 1, -1};
	
	for(int i = 0; i<4; i++){
		
		int newx= x+dx[i];
		int newy = y+dy[i];
		
		if(newx>=0 && newx<m && newy>=0 && newy<n && graph[newx][newy] == 1){
			dfs(newx, newy, graph);
		}
	}
	
}

int worms(int k){
	
	int count = 0;
	
	// initiate a graph
	int graph[50][50] = { 0, };
	
	for(int i = 0; i<k; i++){
		
		int x, y;
		cin >> x >> y;
		graph[x][y] = 1;
			
	}
	
	// dfs with graph;
	for(int i =0; i<m; i++){
		for(int j=0; j<n; j++){
			if(graph[i][j] == 1){
				dfs(i,j, graph);
				count++;
			}
		}
	}
	
	return count;
}

int main(void){
	
	vector<int> answer; // 각 배추밭(t개) 별로 몇 개의 배추벌레 필요한지 저장
	int t, k;
	cin >> t;
	
	for(int a = 0; a<t; a++){
		cin >> m >> n >> k;
		answer.push_back(worms(k));
	}
	
	for(int i = 0; i<answer.size(); i++){
		cout << answer[i] << endl;
	}
}