BOJ 1012 — 유기농 배추

문제설계

2D 격자에서 배추 위치가 주어지고,

상하좌우로 연결된 배추 묶음마다 지렁이 1마리가 필요하다.

결국 서로 연결된 배추 그룹의 개수를 세는 문제.

 

생각한 문제 패턴

격자에서 상하좌우 연결을 보는 순간 그래프 탐색 문제라고 판단은 함.

연결 요소 개수 세기 유형으로 DFS/BFS를 사용해야 하는 문제.

근데 DFS BFS에 대해서 로직에 대해 확장성 등이 익숙하지 않아서 어떻게 설계해야 할지 막힘 

 

첫 접근했을 때 생각

방문 여부를 어떻게 처리해야 하는지가 가장 먼저 고민됨.

visited 배열을 써야 하나, 값을 바꿔야 하나 헷갈렸고,

DFS/BFS 중 무엇을 써야 하는지도 명확하지 않았음.

DFS BFS에 대한 로직 자체의 변형 등의 확장성에 익숙하지 않음

 

 내가 생각한 알고리즘 설명

배추를 발견하면 DFS/BFS를 시작해서 연결된 배추를 전부 방문 처리한다.

한 번의 탐색이 하나의 배추 그룹을 제거하는 과정이므로

탐색 시작 횟수가 곧 정답.

 

실제로 막혔던 지점 

1. DFS에 2D vector를 값 복사로 넘겨서 방문 처리가 반영되지 않음

항상 사용할때 call by value 가 아닌 call by reference로 넘기기

 

2. BFS에서 방문 처리를 언제 해야 하는지(push vs pop) 이해 부족

BFS - > queue

DFS -> stack (재귀)

 

3. 경계 조건 엄밀하게

격자 범위 넘어갈때는 패스하도록 하는 로직에 대해서 인덱스 범위 엄밀하게 처리

 

4. DFS/BFS는 탐색 논리, 로직 구현에 있어서 방법은 다양하다. 아이디어가 중요함 

- 시작점

- 연결된 곳의 이동

- 방문한 곳은 다시 이동하지 않도록 사전 처리 

 

문제 해결

방문 처리는 BFS/DFS 공통 핵심이며 방식만 다르다는 점 이해

 

BFS는 스택과 달리 다른 요소에서 중복으로 탐색할 가능성이 있으므로
큐에 넣는 순간 방문 처리

 

격자 문제에서는 visited 배열 없이 값을 0으로 바꿔도 된다는 것 이해

visited라는 bool 변수를 두어도 되지만 간선을 0으로 바꾸거나 하는 방식으로도 충분히 처리 가능

but, 상황에 따라서 bool 변수를 두는게 좋은지, 아니면 단순 0으로 바꿔서 탐색시 pss하도록 하는게 좋을지는 

노하우가 쌓여야 할 부분인듯

 

DFS/BFS는 문법이나 템플릿이 아니라 탐색 구조라는 알고리즘이다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};



//복사, 참조로 넘겨야 함 
void dfs(int n, int m, vector<vector<int>> &land)
{
	land[n][m] = 0; //visited 마킹

	for(int i=0; i<4; i++)
	{
		int x = n;
		int y = m;
		
		x = x + dx[i];
		y = y + dy[i];

		if(x<0 || x>=land.size() || y<0 || y>= land[0].size()) continue;

		//해당 값이 1일때만 넘어가도록 체크 
		else if(land[x][y] ==1) dfs(x,y, land); 
	}

}


void bfs(int n, int m, vector<vector<int>> &land)
{
	queue<pair<int,int>> q;

	q.push({n,m});
	land[n][m] = 0;

	while(!q.empty())
	{
		auto [x,y] = q.front();
		q.pop();

		for(int i=0; i<4; i++)
		{
			int X = x + dx[i];
			int Y = y + dy[i];

			//경계값 확인
			if(X<0 || X>=land.size() || Y<0 || Y>=land[0].size()) continue;
			else if(land[X][Y] == 1) 
			{
				//bfs면 다른 queue에서 해당 코드 사전에 0처리 안될시 중복 큐되므로 dfs랑 다르게 사전에 0으로 바꿔주어야 함 
				land[X][Y] = 0;
				q.push({X,Y});
				
			} 
			
		}
	}
	


}


int main()
{
	int T;
	cin>>T;

	for(int i=0; i<T; i++)
	{
		int M, N, K;

		cin>>M>>N>>K;

		vector<vector<int>> land(N, vector<int> (M,0));

		for(int j=0; j<K; j++)
		{
			int x,y;
			cin>>x>>y;

			land[y][x] = 1;
		}

		int cnt = 0;

		for(int i=0; i<N; i++)
		{
			for(int j=0; j<M; j++)
			{
				if(land[i][j] ==1)
				{
					cnt++;
		
					bfs(i, j, land);
				}
			}
			
		}

		cout<<cnt<<'\n';
	}
}