[백준] 1012번 유기농 배추

 유기농 배추에 배추흰지렁이의 마리 수를 구하는 문제이다. 이 문제를 풀기위해서 완전탐색을 이용했는데,

먼저 ground 2차원 배열을 생성해서 배추의 위치를 1로 표현을 해주었다. 

그 다음으로 groundN 함수를 사용해 groundN함수를 호출 했을 때 ground[x][y]의 위치가 1이면 배추가 있는 곳이므로 다시 탐색을 시도했을 때 탐색을 하지 않게 하기위해 1에서 0으로 바꿔주었다. 또한 이어져있는 배추를 확인하기 위해

[0,1] [1,0] [-1,0] [0,-1]. 동서남북으로 다시 탐색을 해줘, 그곳에도 배추가 있으면 또 탐색을 못하도록 1에서 0으로 값을 계속 바꾸어주었다. 이렇게 하면 나중에 ground배열에서 배추가 있는 위치를 찾을 때 또 다시 찾을 수 없도록 해줄 수 있기 때문이다.

 

개선해야할 점: 이 문제는 완전탐색 dfs 방식을 이용하면 금방 풀 수 있기 때문에 간단하였다. dfs에서 완전탐색을 시도할때 다음부터는 for문을 이용해서 dfs를 호출 할 수 있도록 개선해야겠다. 

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
int ground[50][50] = { 0 };
int N, M, K;
int cnt = 0;
int groundN(int x, int y) {
	if (x >= N || y >= M || x<0 || y<0) {
		return 0;
	}
	if (ground[x][y] == 1) {
		ground[x][y] = 0;

	}
	
	else if (ground[x][y] == 0) {
		return 0;
	}
	groundN(x + 1, y);
	groundN(x, y + 1);
	groundN(x - 1, y);
	groundN(x, y - 1);

	return 0;
}
void init() {
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 50; j++) {
			ground[i][j] = 0;
		}
	}
}
int main() {
	int tc;
	cin >> tc;
	vector<int> result;
	while (tc--) {
		init();
		int res = 0;
		cin >> N >> M >> K;
		for (int i = 0; i < K; i++) {
			int X, Y;
			cin >> X >> Y;
			ground[X][Y] = 1;
			
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (ground[i][j] == 1) {
					res++;
					groundN(i, j);
				}
			}
		}
		
		result.push_back(res);

	}
	
	for (int i = 0; i < (int)result.size() ; i++) {
		if (i < ((int)result.size() - 1)) {
			cout << result[i] << endl;
		}
		else { cout << result[i]; }
	}
}

 

소스위치: https://github.com/withseungryu/Algorithms/blob/master/BackJoon/1012.cpp

withseungryu/Algorithms

궁금하신 것이 있으시다면 언제든지 댓글로 남겨주세요!~