1012.유기농 배추

이번에 풀어볼 문제는 백준의 1012 유기농 배추이다! 이 문제는 BFS나 DFS를 이용해서 풀면 되는데

역시나 난이도는 높지않다. 여기서 배울 점은 나눠진 영역의 탐색(BFS, DFS)을 진행하는 방법이다.

BFS를 기준으로 설명을 적어놓았다 -> DFS든 BFS든 탐색방법만 다를 뿐 구현 로직은 같다.

1012번: 유기농 배추

이 문제에서 Key Point는 1. 맵에 배추를 잘 넣어주는 로직과 2. 영역별로 나눠져 있는 배추를 탐색하는 것이다. 

---

1번은 간단하기 때문에 조금만 생각하면 가능니까 PASS하고

2번의 경우는 map에 배추부분을 "1"이라는 숫자로 표현해놓고 탐색으로 발견될 때마다 map의 "1"을 지워주며 탐색하는 것이다. 

그렇게 되면 map을 전부 탐색하며 배추 부분만 찾게될 것이고 붙어있는 배추끼리는 이미 BFS 함수를 통해 배추표시가

"1" -> "0"으로 지워져있기 때문에 몇가지 영역으로 나눠있는지 확인할 수 있게된다. 마지막엔 당연히 map의 배추가 다 지워진다.

< Code 설명 - DFS>

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#define MAX 51

using namespace std;
int t, m, n, k;

int map[MAX][MAX];

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

void zilong(int a, int b){
	map[a][b] = 0; // 배추를 만나면 해당배추는 벌레가 갔으므로 0으로 셋팅
	queue<pair<int, int>>bechu; //BFS 탐색을 위한 queue
	bechu.push(make_pair(a, b));//해당 배추좌표를 시작으로 하기위해 queue에 넣음
	while (!bechu.empty()){
		int x = bechu.front().first; // x좌표 이용
		int y = bechu.front().second;// y좌표 이용
		bechu.pop();
		for (int i = 0; i < 4; i++){ // 상하좌우 탐색
			int ax = x + dx[i];
			int ay = y + dy[i];
			if (ax < 0 || ay < 0 || ax >= m || ay >= n)
				continue; // map 범위 내에 없으면 넘김
			if (map[ax][ay] == 1){ // 배추가 있으면
				map[ax][ay] = 0;   // 배추를 0으로 바꿔주고
				bechu.push(make_pair(ax, ay)); 
                                // 해당 좌표 queue에 저장
			}
		}
	}
}

int main(){
	//freopen("1012.txt", "r", stdin);
	cin >> t;
	
	int a, b, cnt;
	for (int z = 0; z < t; z++){
		cin >> m >> n >> k;
		cnt = 0;
		memset(map, 0, sizeof(map));   //map 초기화

		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				map[i][j] = 0; // 우선 전부다 0으로 저장한다.
			}
		}

		for (int i = 0; i < k; i++){
			cin >> a >> b;
			map[a][b] = 1; // 배추가 있는 곳은 1로 저장
		}

		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				if (map[i][j] == 1){ // 배추가 있는 곳은
					zilong(i, j);    // 탐색을 시작한다.
					cnt+=1; 
                    // 탐색중에 배추를 찾으면 map[i][j]=0이 됨
                    // 그러므로 영역을 구분할 수 있다.
				}
			}
		}
		cout << cnt << "\n";
	}
	return 0;
}

 

 

 

 

---

 

 

< Code 설명 - BFS>

#pragma warning(disable:4996)
#include <iostream>
#include <string.h>
#include <stack>


#define MAX 51
using namespace std;


int t, m, n, k;
int map[MAX][MAX];

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

void search(int a, int b){
	map[a][b] = 0;
	stack<pair<int, int>>s;
	s.push(make_pair(a,b));
	int x = s.top().first;
	int y = s.top().second;
	while (!s.empty()){
		for (int i = 0; i < 4; i++){
			int ax = x + dx[i];
			int ay = y + dy[i];
			if (ax < 0 || ay < 0 || ax > m || ay > n)
				continue;
			if (map[ax][ay] == 1){
				map[ax][ay] = 0;
				s.push(make_pair(ax, ay));
				x = s.top().first;
				y = s.top().second;
				i = -1;
			}
		}
		if (!s.empty()){
			s.pop();
			if (!s.empty()){
				x = s.top().first;
				y = s.top().second;
			}
		}

	}
}
int main() {
	//freopen("1012.txt", "r", stdin);
	cin >> t;
	int cnt;
	for (int z = 0; z < t; z++){
		cin >> m >> n >> k;
		cnt = 0;
		memset(map, 0, sizeof(map));
		
		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				map[i][j] = 0;
			}
		}
		int a, b;
		for (int i = 0; i < k; i++){
			cin >> a >> b;
			map[a][b] = 1;
		}

		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				if (map[i][j] == 1){
					search(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << "\n";
	}
	return 0;
}

# BFS 대신 DFS를 쓰는 것말고 나머지는 같으므로 설명은 생략하겠다..

 

 

 

---

 

 

< Code 설명 - 재귀>

#pragma warning(disable:4996)
#include <iostream>
#include <string.h>
#include <queue>


#define MAX 51
using namespace std;


int t, m, n, k;
int map[MAX][MAX];

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

queue<pair<int, int>>q;
void search(int a, int b){
	if (q.empty())
		return;
	map[a][b] = 0;
	int x = q.front().first;
	int y = q.front().second;
	q.pop();
	for (int i = 0; i < 4; i++){
		int ax = x + dx[i];
		int ay = y + dy[i];
		if (ax<0 || ay<0 || ax>=m || ay>=n)
			continue;
		if (map[ax][ay] == 1){
			map[ax][ay] = 0;
			q.push(make_pair(ax, ay));
			search(ax, ay);
		}
	}
}
int main() {
	//freopen("1012.txt", "r", stdin);
	cin >> t;
	int cnt;
	for (int z = 0; z < t; z++){
		cin >> m >> n >> k;
		cnt = 0;
		memset(map, 0, sizeof(map));

		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				map[i][j] = 0;
			}
		}
		int a, b;
		for (int i = 0; i < k; i++){
			cin >> a >> b;
			map[a][b] = 1;
		}

		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				if (map[i][j] == 1){
					q.push(make_pair(i, j));
					search(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << "\n";
	}
	return 0;
}

# 요것도 똑같다:)