백준 1012번 : 유기농 배추

문제 접근

---

나는 바보다 ㅎ헤헿. 문제 똑바로 이해 안 하고 구현하다가 잘 안 돼서 다시 읽어보니 잘 못 풀고 있었다. 문제 제대로 이해하자마자 바로 풀었다. 허무하다. 원리는 간단하다. 입력받고 배추가 있는 곳은 true로 설정했다. find 함수에서 주변에 true 가 있으면, 재귀로 들어가서 지운다. 끝!

 

처음에는 while 문으로 한번에 처리하려고 했는데 시간 초과가 나왔다. 그래서 false로 바꾸는 방식을 한 번에 하는 게 아니라 find 함수로 하나하나 조건 확인해보며 재귀로 분할해서 처리하니 제 시간 안에 풀렸다.

 

오늘의 교훈>

1. 문제를 똑바로 이해하고 풀자.

2. 문제는 분할할 수 있다면 분할해서 처리하자. (재귀 좋아영)

 

 

문제 코드

---

#include <iostream>

using namespace std;

bool field[52][52]={false};

void find(int x, int y)
{
	field[x][y]=false;
	
	if(field[x+1][y])
		find(x+1,y);
	if(field[x][y+1])
		find(x,y+1);
	if(field[x-1][y])
		find(x-1,y);
	if(field[x][y-1])
		find(x,y-1);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T, M, N, K, x, y, ans;
	
	cin>>T;
	
	for(int i=0; i<T; ++i)
	{
		ans = 0;
		
		cin>>M>>N>>K;
		
		for(int j=0; j<K; ++j)
		{
			cin>>x>>y;
			field[x+1][y+1]=true;
		}
		
		for(int j=1; j<N+1; ++j)
			for(int k=1; k<M+1; ++k)
				if(field[k][j])
				{
					++ans;
					find(k,j);
				}
		
		cout<<ans<<'\n';
	}
}

 

결과

---