[BOJ] 2667 단지번호붙이기

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

Note

4 - Connectivity로 몇개의 개체가 존재 하는지 크기는 얼마인지 오름차순으로 나열하는 문제
입력이 띄어쓰기로 들어오는것이 아닌 line 단위로 들어오는점에 유의하여야한다.

n이 25로 제한되므로
최대 개체의 수는 313개 ( 25 * 12 + 13 )

위치를 저장하는 Queue와 구조체를 이용하면 간단히 풀린다.

알고리즘

1. (0,0) 에서 (n-1 , n-1) 까지 반복
2. 현재 조회 지점이 방문 기록이 없고 1이면 BFS 진행
   2.1 현재 지점을 방문 한것으로 변경
   2.2 현재 지점과 연결된 점을 Queue에 추가
   2.3 현재 번호에 해당하는 개체의 크기를 1 추가
3. 개체 크기를 저장한 배열을 정렬
4. 개체의 개수를 출력 후 정렬된 개체 크기 배열을 출력

소스코드

#include <iostream>

using namespace std;

const short MAX_SIZE = 625;

struct mPoint {
	short x;
	short y;
	
	mPoint() {}
	mPoint(short x, short y) : x(x), y(y) {}
};

short map[25][25];
bool checker[25][25];
mPoint q[MAX_SIZE];
int head = 0;
int tail = 0;
const short posX[4] = { 1, 0 , -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };

void push(short x, short y) {
	q[head++ % MAX_SIZE] = mPoint(x, y);
}

mPoint pop() {
	return q[tail++ % MAX_SIZE];
}

bool isEmpty() {
	return head == tail;
}

int main()
{
	int n;
	int number = 0;
	int sizeList[313];

	cin >> n;

	fill_n(sizeList, 313, 0);

	for (int i = 0; i < n; i++)
	{
		char line[26];
		cin >> line;
		for (int j = 0; j < n; j++)
			map[i][j] = int(line[j] - '0');
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (checker[i][j] || map[i][j] == 0)
				continue;

			push(i, j);

			// BFS
			while (!isEmpty())
			{
				mPoint cur = pop();

				if (checker[cur.x][cur.y])
					continue;

				checker[cur.x][cur.y] = true;
				sizeList[number]++;

				for (int k = 0; k < 4; k++)
				{
					short nextX = cur.x + posX[k];
					short nextY = cur.y + posY[k];
					if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n)
						if (map[nextX][nextY] == 1)
							push(nextX, nextY);
				}
					
			}

			number++;
		}
	}

	// Selection Sort
	for (int i = 0; i < number; i++)
	{
		int min = i;
		for (int j = i; j < number; j++)
			if (sizeList[min] > sizeList[j])
				min = j;
		swap(sizeList[min], sizeList[i]);
	}

	cout << number << '\n';
	for (int i = 0; i < number; i++)
		cout << sizeList[i] << '\n';

	return 0;
}

2019-01-05 19:24:36에 Tistory에서 작성되었습니다.