[BFS]03-백준 1012 유기농 배추

**5백준1012번 유기농배추**

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

1012번: 유기농 배추

 

---

 

정답 코딩

#include<iostream>
#include <queue>
using namespace std;

int M,N;			//가로, 세로 
int K;				//배추 개수
int arr[51][51];	//배추존재여부
int worms=0;			//필요한배추흰지렁이개수
queue<pair<int,int> > q;
int TC;				//테스트케이스
int visit[51][51];	//방문여부

int xc[4]={-1,1,0,0};	//좌우상하 인접확인
int yc[4]={0,0,-1,1};


int bfs(int x, int y){			//시작지점부터 bfs실행
	q.push(make_pair(x,y));
	visit[x][y]=1;
	while(!q.empty()){
		int dx=q.front().first;
		int dy=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			/*	인접4면 중 배추가 있고 방문하지 않았으면	*/
			if((arr[dx + xc[i]][dy + yc[i]]==1) && (visit[dx + xc[i]][dy + yc[i]]==0)){
				q.push(make_pair(dx + xc[i],dy + yc[i]));
				visit[dx + xc[i]][dy + yc[i]]=1;
			}

		}
	}worms++;		//지렁이 증가
	return 0;
}

int input(){		//입력 함수 
	cin>>M>>N>>K;	
	for(int i=0;i<K;i++){
		int sx,sy;
		cin>>sx>>sy;
		arr[sx][sy]=1;
	}
	return 0;
}

int main(){
	cin>>TC;
	for(int i=0;i<TC;i++){	
		input();	//테스트케이스 크기만큼 입력
		
		for(int j=0;j<M;j++){
			for(int k=0;k<N;k++){
				if(arr[j][k]==1 && visit[j][k]==0 ) bfs(j,k);
			}
		}
	cout<<worms<<"마리 필요"<<endl;
	worms=0;
	}
	return 0;
}

 

---

 

 

처음 문제를 접했을 때 입력에 대해 이해를 못해서 예제를 확인해야 했다. (테스트 케이스가 있는 문제도 처음 다뤄봤다.)

무조건적으로 BFS를 응용해야지라는 생각을 접하니 막막하고 이전 문제에서 정답을 자꾸 유추하려 했다.

결국엔 배추흰지렁이가 필요한  영역의 개수를 파악해야하는 데 각 영역에서 bfs가 개별로 이루어지는 것이다.

그리고 bfs가 이루어진 횟수만큼 지렁이의 개수를 증가시키면 된다.

여러 개의 큐를 동시에 써야되나? 라고 생각하긴 했지만 결국 순차적으로 방문여부를 조사하면서 확인하면 되는 간단한 문제였다.

항상 접했을 때는 막막하고 어려운데 풀고 나면 참 쉬워보인다. 많이 연습해야지! 

p.s 글쓰기에서는 코딩 입력이 참 깔끔하고 알록달록 이쁘게 정리되는데 왜 완료해서 업로드하면 초라하게 바뀌는 거지? 티스토리 별루당

 

아래 예제의  땅

테스트 출력 콘솔