백준-1012번 - 유기농 배추

내가 백준 문제를 풀면서 느낀 점은 채점을 할 때 맞게 하고 싶다면 문제에서 변수들을 잘 파악해야한다는 것이다. 

우선 문제를 살펴보면 

테스트 케이스를 의미하는 변수 T가 존재한다. 

또한 배추를 심은 배추밭의 가로길이 M, 세로 길이 N, 배추를 심은 개수 K가 존재한다. 

또한 그 후 배추의 위치를 나타내는 변수론느 x, y가 존재한다. 

그럼 일단 6개의 변수가 존재하는 것이다. 그 후 반복문 안에서 다음 배열 인덱스를 담아 줄 ny, nx변수와 최종 개수를 ret할 ret 변수까지 9개가 존재한다. 

또한 이 문제는 깊이 탐색 문제이므로 배추의 위치를 표현할 map과 그 배열과 같은 크기의 방문 여부 배열이 필요하다. 

#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;

int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int m,n,k;// 배추 밭 넓이와 배추
int ret;
int x, y; // 배추
int ny, nx;//넥스트 배추  
int t;
int a[51][51];
bool visited[51][51];
void dfs(int y, int x){
	visited[y][x] = 1;
	for(int i=0;i<4;i++){
		ny = y + dy[i];
		nx = x + dx[i];
		if(ny<0||ny > 51 || nx < 0 || nx> 51)continue;
		if(a[ny][nx] == 1 && visited[ny][nx] == 0){
			dfs(ny, nx);
		}
	}
	return;
} 
int main() {
	cin.tie(NULL);
	cin.tie(NULL);
	cin >> t;
	while(t--){
		fill(&a[0][0], &a[0][0] + 51 * 51, 0); // 0으로 초기화
		fill(&visited[0][0], &visited[0][0]+ 51 * 51, 0); // 0으로 초기화 
		ret= 0;
		cin >> m >> n >> k;
		for(int i = 0; i < k; i++)
		{
			cin >> x >> y;
			a[y][x] = 1;
		}
		for(int i=0;i < n;i++){
			for(int j = 0; j < m; j++){
				if(a[i][j] == 1 && visited[i][j] == 0)
				{
					dfs(i, j);
					ret++;
				}
			}
		}
	cout << ret << endl;	
	}
	
	
	return 0;
}

내가 작성한 정답은 다음과 같다. 우선 dfs라는 함수를 만들어준 후 위치를 받고 그 안에서 4방향을 탐색하면서 visited배열의 값을 바꿔주며 이동하는 방식이다. 그 후 main문안에서는 그저 문제가 요구하는 흐름대로 전체 t번 반복하면 되고 입력 받는대로 입력을 받고 dfs함수를 실행하는 수를 세어 ret++를 해주면 된다. 

 

내가 이 문제에서 배운 새로운 함수는 fill이라는 함수인데 내가 고민하던 여러 데이터가 들어갈 수 있는 자료구조를 특정한 값으로 초기화 해줄 수 있는 함수라고 한다. 

사용법은 다음과 같다. 

 

fill( 시작점 iterator, 끝 iterator, 초기화 하고 싶은 값);

 

나는 2차원 배열을 0이라는 값으로 초기화 시키고 싶었으므로 fill(&a[0][0], &a[0][0]+ 51 * 51, 0)과 같이 작성해주었다.