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

출처 

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

2667번: 단지번호붙이기

 내 풀이 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

//너비 우선 탐색에 필요한 변수들 dx,dy = 상하좌우 움직일 때 사용 
int BFS(int start, int end);
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

//지도 크기, 방문 여부 
int map[26][26];
bool visited[26][26];

int total_apart = 0;	//총 아파트 수
vector<int>result;		//세대 수 

int N = 0;	//정사각형 크기
string change = " ";

int main()
{
	cin >> N;
	//입력받은 문자열을 다시 int형으로 변환 
	for (int i = 0; i < N; i++)
	{
		cin >> change;
		for (int j = 0; j < N; j++)
		{
			map[i][j] = change[j] - '0';
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j] == 1 && !visited[i][j])
			{
				total_apart++;
				result.push_back(BFS(i, j));
			}
		}
	}

	//벡터 정렬 후 출력 
	sort(result.begin(), result.end());

	cout << total_apart << endl;

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}
}

int BFS(int start, int end)
{
	int resident = 1;	//나중에 return 해줄 거주자들 변수
	queue<pair<int, int>> q;
	visited[start][end] = true;
	q.push({ start,end });

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		//상하좌우 이동하면서 집이 있는 곳, 방문안한 곳 확인
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			//범위를 벗어나면 continue
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

			if (map[nx][ny] == 1 && !visited[nx][ny])
			{
				visited[nx][ny] = true;
				q.push({ nx,ny });
				resident++;
			}
		}
	}
	return resident;
}

 

 해설

 정사각형 N의 크기를 입력받고 문자열을 정수형으로 변경해준 뒤 다시 한번 N의 크기만큼 반복문을 실행하여 만일 방문하지 않았고 1(집이 있는 경우)일 경우 total_apart(총 단지 수)를 증가시키고 BFS 함수를 실행하여 상하좌우 연결되어 있는 같은 단지 내 집의 수를 벡터 변수안에 넣어주었다.  반복문이 종료되면 정렬 후 총 단지 수와 정렬된 단지 내 집의 수를 출력해주었다.

 

 새로 안 것 

전에 풀어 보았던 BFS 문제 복습