[백준 1012번 C/C++] 유기농 배추

 

[백준 1012번 C/C++] 유기농 배추

 

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

1012번: 유기농 배추

---

 

 

해결전략

 

깊이 우선 탐색 DFS

너비 우선 탐색 BFS

 

둘 다 가능하다

 

 

---

 

DFS 풀이

 

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int t; //t 테스트 케이스의 개수
int m, n, k; //m 가로길이, n 세로길이, k 위치의 개수

int cnt;

vector<vector<int>> v;
map<pair<int, int>, bool> myMap;

int dirY[4] = { -1, 0, 1 ,0 };
int dirX[4] = { 0, -1, 0 ,1 };

void DFS(int y, int x)
{
	for(int i=0; i<4; i++)
	{
		int newY = y + dirY[i];
		int newX = x + dirX[i];

		if (0<=newY && 0<=newX && newY<n && newX<m)
		{
			v[y][x] = 0;

			if (v[newY][newX] == 1)
			{
				//cout << "newY: " << newY << "  newX: " << newX << "\n";
				
                //새로운 배추 위치를 찾은 후 myMap의 bool 값을 false로 변경한다.
                //false로 변경하는 이유는? 밑에서 DFS를 중복으로 도는걸 방지한다.
				if (myMap.find({ newY, newX }) == myMap.end())
					myMap[{newY, newX}] = false;

				cnt--;//최대 배추흰지렁이 마리수에서 -1 해준다
				DFS(newY, newX);//새로 찾은 배추 위치에서 DFS 시작
			}
		}	
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	int x, y;

	while(t--)
	{
		cin >> m >> n >> k;
		
		myMap.clear();
        v.clear();
		v.resize(n, vector<int>(m, 0));

		cnt = k;//최대 배추흰지렁이 마리 수

		//배추 위치 입력
		for (int i=0; i<k; i++){
			cin >> x >> y;
			v[y][x] = 1;//배추 위치는 1, 빈칸은 0

			//배추 위치 map에 기록
			myMap.insert(make_pair(make_pair(y, x), true));
		}
		

		if(myMap.size() == 0 || myMap.size() == 1){
			cout << cnt << "\n";
		}
		else
		{
        	//myMap 사이즈 만큼 for문을 돌며 조건에 맞으면 DFS를 돈다.
			for (pair<const pair<int, int>, bool>& iter : myMap)
			{
            	//myMap의 bool값이 true인 경우 DFS를 시작한다.
				if (iter.second == true)
				{
					//cout << "y : " << iter.first.first << " x : " << iter.first.second << "\n";
					DFS(iter.first.first, iter.first.second);
				}
			}

			cout << cnt << "\n";
		}
	}


	return 0;
}

 

v.clear();

myMap.clear();

행렬과 맵의 초기화를 해줘야 한다. 주의하자.

---

 

 

BFS 풀이

 

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

int t; //t 테스트 케이스의 개수
int m, n, k; //m 가로길이, n 세로길이, k 위치의 개수

int cnt;

vector<vector<int>> v;
queue<int> Q;

int dirY[4] = { -1, 0, 1 ,0 };
int dirX[4] = { 0, -1, 0 ,1 };

void BFS(int y, int x)
{
	queue<pair<int, int>> Q;
	Q.push({ y, x });

	while (!Q.empty())
	{
		int curY = Q.front().first;
		int curX = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int newY = curY + dirY[i];
			int newX = curX + dirX[i];

			if (0 <= newY && newY < n && 0 <= newX && newX < m)
			{
				// 아직 방문하지 않은 배추 위치
				if (v[newY][newX] == 1)
				{
					v[newY][newX] = 0;
					Q.push({ newY, newX });
				}
			}//if
		}//for
	}//while

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	int x, y;

	while(t--)
	{
		cin >> m >> n >> k;
		
		v.resize(n, vector<int>(m, 0));

		cnt = 0;//필요한 배추흰지렁이 마리 수 초기화

		//배추 위치 입력
		for (int i=0; i<k; i++){
			cin >> x >> y;
			v[y][x] = 1;//배추 위치는 1, 빈칸은 0
			
		}
		
		for(int y = 0; y < n; y++){
			for (int x = 0; x < m; x++) 
			{
				//배추 위치를 발견하면 BFS 실행
				if (v[y][x] == 1)
				{
					cnt++;
					BFS(y, x);
				}
			}
		}

		cout << cnt << "\n";
		v.clear();//행렬 초기화
	}


	return 0;
}

 

 

---