최근 풀이

: 240309

• bfs로 풀었는데,
  vector resize 이슈가 있었음.

vector::resize

• resize를 하더라도 , 이전에 원소에 적용한 값은 그대로다...
  

• 이번에는 작게 해보자.
  

resize를 여러번 해야 할때는 clear 와 함께 사용하자.

언제 풀어봄.

• 220928 08:55 ~ 09:30

220813 최근 풀이

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

// 상하좌우 만들기 
int dx[]{0,0,-1,1};
int dy[]{-1,1,0,0};
int t, n , m, vv;


// 체크 변수 사용해서 
// 이미 수행완료되었으면 bfs 안타게 하자. 
// => bool로 처리함. 
bool bfs(vector<vector<int>>&_v, 
vector<vector<bool>>&_check , int _y , int _x)
{
	if(_check[_y][_x] == true || _v[_y][_x] == 0)
		return false;

	queue<pair<int,int>>q;
	q.push(make_pair(_y, _x));

	while(!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second; 
		q.pop();
		//현재 값 체크해야 함. 
		_check[curY][curX] = true;

		//상하좌우를 확인하면서 이상없으면 삽입
		for(int i = 0; i < 4; ++i)
		{
			int nY = curY + dy[i];
			int nX = curX + dx[i];

			//1. 바깥으로 넘어가는지를 확인해야 함. 
			//2. 인접한 곳이 반드시 1이어야만 함. 
			if(0 <= nY && nY < m
			&&  0 <= nX && nX < n )
			{
				//1번 조건
				if(_check[nY][nX] == true)
					continue;
				//2번 조건
				if(_v[nY][nX] == 0)
					continue;
				_check[nY][nX] = true;
				q.push(make_pair(nY, nX));
				
			}

		}


	}
	return true;
}


int main()
{
	freopen("input.txt", "r", stdin);
	

	cin >> t;

	while(t--)
	{
		cin >> n>> m >> vv;

		vector<vector<int>>v(m, vector<int>(n));
		vector<vector<bool>>check(m, vector<bool>(n, false));

		for(int i = 0; i < vv; ++i)
		{
			int a, b;
			cin >> a >> b;
			v[b][a] = 1;
		}

		// 모든 원소를 돌려야함.
		int res = 0;
		for(int i = 0; i < m; ++i)
		{
			for(int j = 0; j < n; ++j)
			{
				// 원소의 값이 1인 값만 들어와야 함.
				if(v[i][j] == 1)
				{
					if(bfs(v, check, i , j))
					{
						++res;
					}
				}
				
			}
		}
		cout << res << endl;
		// 출력용
		//for(int i = 0; i < m; ++i)
		//{
		//	for(int j = 0; j < n; ++j)
		//	{
		//		cout << v[i][j] <<" ";
		//	}
		//	cout << endl;
		//}


	}

}

최근 풀이

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

#include <vector>
#include <queue>

int m, n, k;
// m : 가로 , n : 세로

bool dfs(int _y, int _x, vector<vector<int>>&_v)
{
	//상하좌우를 순차적으로 진행

	//조건 처리 중요함.
	if (_y < 0 || _y >= n
		|| _x < 0 || _x >= m)
		return false;

	if (_v[_y][_x] == 0)
		return false;

	{
		_v[_y][_x] = 0;
		// 상
		dfs(_y - 1, _x, _v);

		// 하
		dfs(_y + 1, _x, _v);

		// 좌
		dfs(_y, _x - 1, _v);

		// 우
		dfs(_y, _x + 1, _v);
	}
	
	return true;
}


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

	for (int a = 0; a < t; ++a)
	{
		
		// m : 가로 , n : 세로
		cin >> m >> n >> k;

		vector<vector<int>>v(n, vector<int>(m, 0));

		for (int b = 0; b < k; ++b)
		{
			int x, y;
			cin >> x >> y;

			v[y][x] = 1;
		}
		
		//맞게 들어왔는지 확인하자. 
		//for (int c = 0; c < n; ++c)
		//{
		//	for (int d = 0; d < m; ++d)
		//	{
		//		cout << v[c][d];
		//	}
		//	cout << endl;
		//}

		// 재귀를 통해 처리하자.
		// 1인 값일 경우에 함수로 진입하고, 
		// 상하좌우가 1일 경우에 인덱스 증감하면서 
		//다시 한번 재귀로 진입과 동시에 기존값을 0으로 변경
		// 모든 2차원 인덱스의 번호로 재귀를 돌리면서 진행함.
		// 재귀 완료 시 마지막 뛰쳐 나올 때 카운팅 
		int cnt{ 0 };
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (dfs(i, j, v) == true)
					cnt++;
			}
		}
		cout << cnt << endl;;
	}
	
	


}

---

이전 풀이

• 문제에서 제시한 것과 다름 : 가로와 세로가 반전됨.

bfs 풀이

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

//dfs로도 풀어보자 
bool bfs(vector<vector<int>>&v , vector<vector<int>>&check , int posX, int posY)
{
	if (check[posY][posX])
		return false;

	//상하좌우
	int dy[4] = { 1,-1,0,0 };
	int dx[4] = { 0,0,-1,1 };

	
	queue<pair<int, int>>q;
	q.push({ posY,posX });
	

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

		q.pop();

		if (check[curY][curX])
			continue;
		check[curY][curX] = 1;

		for (int i = 0; i < 4; i++)
		{
			int nY = curY + dy[i];
			int nX = curX + dx[i];

			if (nY < 0 || nY >= v.size()
				|| nX < 0 || nX >= v[0].size())
				continue;

			if (v[nY][nX] != 1)
				continue;

			if (check[nY][nX])
				continue;

			q.push({ nY, nX });

		}

	}

	return true;
}


int main() {

	
	int cnt;
	cin >> cnt;

	for (int t = 0; t < cnt; t++)
	{
		int answer = 0;
		int n, m, k;
		cin >> n >> m >> k;

		vector<vector<int>>v(n, vector<int>(m, 0));
		vector<vector<int>>check(n, vector<int>(m, false));
		for (int i = 0; i < k; i++)
		{
			int a, b;
			cin >> a >> b;
			v[a][b] = 1;
		}

		//불변수를 체크해서
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				
				if (v[i][j] != 1)
					continue;
				if (bfs(v, check, j, i))
				{
					answer++;
				}
			}
		}
		cout << answer << endl;

	}
	


	return 0;
}

dfs 풀이

#include <vector>
#include <iostream>

using namespace std;

int m, n, k;

bool dfs(vector<vector<int>>&v , int y, int x)
{
	

	if (x < 0 || x >= n
		|| y < 0 || y >= m)
		return false;

	if (v[y][x] == 0)
		return false;

	v[y][x] = 0;
	dfs(v, y + 1, x);
	dfs(v, y - 1, x);
	dfs(v, y, x + 1);
	dfs(v, y, x - 1);

	return true;

}


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

	
	for (int i = 0; i < t; i++)
	{
		
		cin >> m >> n >> k;
		
		vector<vector<int>>v(m, vector<int>(n));

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

		int cnt = 0;
		//dfs로 가자.
		for (int z = 0; z < m; z++)
		{
			for (int x = 0; x < n; x++)
			{
				if (dfs(v, z, x))
				{
					cnt++;
				}
			}
		}

		cout << cnt << endl;

	}


}