백준 2667 단지번호붙이기(c++)

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

2667번: 단지번호붙이기

<코드> (스택 쓰지 않고 풀기)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
bool check[26][26];
int Board[26][26];
vector<int>rooms;
int cnt=0;
int n;
string s;
void dfs(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		int sr = x + mov[i][0];
		int sc = y + mov[i][1];
		if(sr >=0 && sc >=0 && sr <= n && sc <= n){
		if(!check[sr][sc] && Board[sr][sc]){
			check[sr][sc] = true;
			cnt++;
			dfs(sr,sc);		
		}
	}
	
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		for(int j=0;j<n;j++)
		{
			Board[i][j]=s[j]-'0';
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(!check[i][j] && Board[i][j]){
				check[i][j] = true;
				cnt++;
				dfs(i,j);
				rooms.push_back(cnt);
				cnt=0;
				
			}
		}
	}
	cout<<rooms.size()<<'\n';
	sort(rooms.begin(),rooms.end());
	for(int i=0;i<rooms.size();i++){
		cout<<rooms[i]<<'\n';
	}
}

 

<코드2, 스택을 이용한 풀이>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
bool check[26][26];
int Board[26][26];
stack<pair<int,int>>rooms;
vector<int>v;
string s;
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		for(int j=0;j<n;j++)
		{
			Board[i][j]=s[j]-'0';
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(!check[i][j] && Board[i][j]){
				check[i][j] = true;
				int cnt=1;
				rooms.push({i,j});
				while(!rooms.empty()){
					pair<int,int> cur = rooms.top();
					rooms.pop();
					for(int i=0;i<4;i++)
					{
						int sr = cur.first + mov[i][0];
						int sc = cur.second + mov[i][1];
						if(sr < 0 || sc < 0 || sr > n || sc > n) continue;
						if(!Board[sr][sc] || check[sr][sc]) continue;
						check[sr][sc] = true;
						rooms.push({sr,sc}); cnt++;
					}
				}
				v.push_back(cnt);	
			}
			
		}
	}
	cout<<v.size()<<'\n';
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		cout<<v[i]<<'\n';
	}
}

이 문제는 dfs를 이용하여 풀 수 있다. 입력을 문자열로 받아야 하는 것이 핵심이다. 왜냐하면 숫자를 공백없이 입력해야 하기 때문에 하나의 숫자로 바라보기에 문자열로 입력받은 후에, 한 문자당 하나의 숫자로 처리해주는 과정이 필요하다. 우선적으로 각 노드가 방문할 수 있는지의 여부(visited)와 집이 있는지의 여부(Board)를 확인한다. 그리고 dfs의 핵심부분인 방문여부가 false이면 true로 바꿔주고 단지의 개수를 세준 후, 다시 dfs라는 함수를 호출해주 재귀적으로  호출하여 푸는 방법이 있다.

더불어 스택을 이용한 풀이 방법은 재귀적인 방법과는 사뭇 다르다. 스택을 이용한 방법은 while문 처리를 통해서 dfs를 구현할 수 있는데, while문 안에 있는 내용에서 방문 여부 및 집 존재 여부 등을 확인해줄 수 있다.