[백준 2667] 단지번호 붙이기

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

2667번: 단지번호붙이기

문제 요구사항

1. 단지 개수 출력 하기

2. 단지 별 크기 오름차순으로 출력하기

 

 

 

1번 풀이

전체 크기만큼 탐색하여 bfs가 돌입 시점에 단지 개수를 1 증가 시켜준다.

visit배열을 선언하여 아파트가 있고 방문을 안했다면 bfs시작할 수 있도록 한다.

상하좌우로 탐색하여 위 조건일 경우 queue에 넣어 탐색한다.

 

2번 풀이

단지 별 크기를 저장할 배열에 단지 크기를 저장한다.

sort를 이용하여 오름차순으로 정렬한다.

 

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


struct go {
	int x;
	int y;
};

int map[26][26];
int n;
int visit[26][26];
int number[26 * 26];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			char ch;
			scanf(" %c", &ch);
			map[i][j] = ch - '0';
		}
	}

	int cnt = 0;
	int a = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] > 0 && visit[i][j] == 0)
			{
				queue<go> q;
				cnt++;
				visit[i][j] = 1;
				q.push({ i,j });
				int num = 1;
				while (!q.empty())
				{

					int r = q.front().x;
					int c = q.front().y;
					q.pop();
					for (int k = 0; k < 4; k++)
					{
						int nr = r + dr[k];
						int nc = c + dc[k];
						if (nr < 0 || nc < 0 || nr >= n || nc >= n)
							continue;
						if (map[nr][nc] == 1 && visit[nr][nc] == 0)
						{
							num++;
							visit[nr][nc] = 1;
							q.push({ nr,nc });
						}
					}
				}
				number[a] = num;
				a++;
			}
		}
	}
	cout << cnt << endl;
	sort(number, number + a);
	for (int i = 0; i < a; i++)
	{
		cout << number[i] << endl;
	}
}