BaekJoon 2667번: 단지번호붙이기(C++)

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

2667번: 단지번호붙이기

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

 

풀이법

1) DFS와 BFS 어떤 걸로 풀어도 성공할 수 있는 문제이다. 연결되어 있는 것이 있는지가 핵심이고, 공부를 위해 둘다 구현해 보는 것을 추천한다

2) 구현에 어려움이 있는 문제기 보다는, 빠르게 이게 무슨 문제구나를 파악하는 것이 중요한 문제이다.

3) BFS와 DFS의 개념에 대해 알고 있다면, 구현 시에 BFS는 Queue를 DFS는 Stack이나 재귀를 이용하면 된다. 아래 예시를 통해 이해가 부족한 부분이 있다면 공부해 보는 것을 추천한다.

 

 

BFS로 푼 문제

int n;
int arr[26][26];
bool visited[26][26];
int cnt = 0;
vector<int> vec;
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,-1,1,0 };
void bfs(int x, int y)
{
	cnt++;
	int bfsCount = 0;
	queue<pair<int, int>> q;
	q.push({ x,y });
	while (!q.empty())
	{
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		if (visited[tx][ty])
			continue;
		visited[tx][ty] = 1;
		bfsCount++;
		for (int i = 0; i < 4; i++)
		{
			int bx = tx + vx[i];
			int by = ty + vy[i];
			if (bx < 0 || bx >= n || by < 0 || by >= n)
				continue;
			if (arr[bx][by] == 1 && visited[bx][by] == false)
			{
				q.push({ bx,by });
			}
		}
	}
	vec.push_back(bfsCount);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			if (s[j] - '0' == 0)
			{
				arr[i][j] = 0;
			}
			else
				arr[i][j] = 1;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 1 && visited[i][j] == false)
			{
				bfs(i, j);
			}
		}
	}
	cout << cnt<<"\n";
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << "\n";
	}

}

BFS로 푼 문제

int n;
int arr[26][26];
bool visited[26][26];
int cnt = 0;
vector<int> vec;
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,-1,1,0 };
void dfs(int x, int y)
{
	cnt++;
	int dfsCount = 0;
	stack<pair<int, int>> st;
	st.push({ x,y });
	while (!st.empty())
	{
		int tx = st.top().first;
		int ty = st.top().second;
		st.pop();
		if (visited[tx][ty])
			continue;
		visited[tx][ty] = true;
		dfsCount++;
		for (int i = 0; i < 4; i++)
		{
			int bx = tx + vx[i];
			int by = ty + vy[i];
			if (bx < 0 || bx >= n || by < 0 || by >= n)
				continue;
			if (arr[bx][by] == 1 && visited[bx][by] == false)
			{
				st.push({ bx,by });
			}
		}
	}
	vec.push_back(dfsCount);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			if (s[j] - '0' == 0)
			{
				arr[i][j] = 0;
			}
			else
				arr[i][j] = 1;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 1 && visited[i][j] == false)
			{
				dfs(i, j);
			}
		}
	}
	cout << cnt<<"\n";
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << "\n";
	}

}