백준2667번 단지번호 붙이기 C++로 구현해보기

 

```

백준2667번 단지번호 붙이기 C++로 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 2667번 풀이
2.  DFS BFS에 대한 간단한 설명
3.  queue에 대한 간단한 설명

---

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

2667번: 단지번호붙이기

 

 

백준 2667번 단지번호 붙이기의 경우

난이도 쉬움 등급의 문제로서

 

아파트 블럭이 배열 형식으로 주어질 경우

수직 혹은 수평으로 이어진 아파트의 블럭 갯수및 해당 블럭 내에 있는 아파트의 수를 구하는

초등학교올림피아드 문제 입니다.

 

 

요즘 회사생활이 바뻐서 자세하게 설명을 하지는 못했지만 코드를 보시면 이해가 되실겁니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

BFS 와 DFS는 

각 너비 우선 탐색

깊이 우선 탐색으로서

 

자세한 코드 및 설명은 (영문) 여기를 보고 오시면 됩니다

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

Difference between BFS and DFS - GeeksforGeeks

 

큐는

사람들 줄서있는것 처럼 먼저 들어온게 먼저 나가는 거라고 이해 하시면 됩니다.

 

큐를 쓰셔도 되고 스택을 쓰셔도 됩니다.

 

저는 중간에 재귀를 썻습니다.

---

 

일단 해당 문제에서 아파트 단지 사이즈를 입력 받고

입력 받은 아파트 단지 사이즈를 참조해서

 

아파트 지도를 입력받습니다.

 

저는 일단 CMy2DArray라는 클래스를 선언하고

 

class CMy2DArray
{
private:
	int** AptBlock;
	int** VisitedBlock;
	int sizeX;
	int sizeY;
	int BlockCount;
	int BlockTotalCount;
	int dx[4] = { 1,-1,0,0 };
	int dy[4] = { 0, 0,1,-1 };
	int BlockHouseCountArray[625] = {0};
	int BlockHouseCountArrayLength;

public:
	CMy2DArray(int size);
	~CMy2DArray();
	void assignArraySize(int size);
	void keyBoardInputFillArray();
	void displayArray();
	void DFS(int x, int y);
	void checkAllBlock();
	void InsertBlockHouseCountArray(int blockCount);
	void PrintBlockHouseCountArray();
};

 

생성자 와 소멸자를 정의 하였습니다

//생성자
CMy2DArray::CMy2DArray(int size)
{
	this->sizeX = size;
	this->sizeY = size;
	BlockHouseCountArrayLength = 0;
	BlockTotalCount = 0;
	AptBlock = new int* [this->sizeY];
	for (int i = 0; i < this->sizeY; ++i) {
		AptBlock[i] = new int[sizeX];
	}

	VisitedBlock = new int* [this->sizeY];
	for (int i = 0; i < this->sizeY; ++i) {
		VisitedBlock[i] = new int[sizeX];
		for (int j = 0; j < this->sizeX; ++j)
		{
			VisitedBlock[i][j] = 0;
		}
	}


}
// 소멸자
CMy2DArray::~CMy2DArray()
{
	// 메모리 관리
	for (int i = 0; i < sizeY; ++i) {
		delete[] AptBlock[i];
	}
	delete[] AptBlock;

	for (int i = 0; i < sizeY; ++i) {
		delete[] VisitedBlock[i];
	}
	delete[] VisitedBlock;
}

 

메인에서 

int main()
{
	int blockSize;
	cin >> blockSize;
	CMy2DArray *cMy2DArray = new CMy2DArray(blockSize);
	cMy2DArray->keyBoardInputFillArray();
	cMy2DArray->checkAllBlock();
	cMy2DArray->PrintBlockHouseCountArray();
	return 0;
}

blockSize 라는 배열의 크기를 입력 받고

새로운 클래스 객체를 만들어서

 

keyBoardInputFillArray 함수로 지도를 채워주고

 

checkAllBlock 함수로 각 지도 내에 있는 아이템 들을 하나씩 확인하고 DFS를 돌렸습니다.

 

 

 

 

 

전체 코드는 다음과 같습니다

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

class CMy2DArray
{
private:
	int** AptBlock;
	int** VisitedBlock;
	int sizeX;
	int sizeY;
	int BlockCount;
	int BlockTotalCount;
	int dx[4] = { 1,-1,0,0 };
	int dy[4] = { 0, 0,1,-1 };
	int BlockHouseCountArray[625] = {0};
	int BlockHouseCountArrayLength;

public:
	CMy2DArray(int size);
	~CMy2DArray();
	void assignArraySize(int size);
	void keyBoardInputFillArray();
	void displayArray();
	void DFS(int x, int y);
	void checkAllBlock();
	void InsertBlockHouseCountArray(int blockCount);
	void PrintBlockHouseCountArray();
};

//생성자
CMy2DArray::CMy2DArray(int size)
{
	this->sizeX = size;
	this->sizeY = size;
	BlockHouseCountArrayLength = 0;
	BlockTotalCount = 0;
	AptBlock = new int* [this->sizeY];
	for (int i = 0; i < this->sizeY; ++i) {
		AptBlock[i] = new int[sizeX];
	}

	VisitedBlock = new int* [this->sizeY];
	for (int i = 0; i < this->sizeY; ++i) {
		VisitedBlock[i] = new int[sizeX];
		for (int j = 0; j < this->sizeX; ++j)
		{
			VisitedBlock[i][j] = 0;
		}
	}


}
// 소멸자
CMy2DArray::~CMy2DArray()
{
	// 메모리 관리
	for (int i = 0; i < sizeY; ++i) {
		delete[] AptBlock[i];
	}
	delete[] AptBlock;

	for (int i = 0; i < sizeY; ++i) {
		delete[] VisitedBlock[i];
	}
	delete[] VisitedBlock;
}

void  CMy2DArray::keyBoardInputFillArray()
{
	for (int i = 0; i < sizeY; i++)
	{
		string tempStr;
		cin >> tempStr;
		for (int j = 0; j < sizeX; j++)
		{
			AptBlock[i][j] = tempStr[j] - '0';
		}
	}
}

void  CMy2DArray::displayArray()
{
	for (int i = 0; i < sizeY; i++)
	{
		for (int j = 0; j < sizeX; j++)
		{
			cout << AptBlock[i][j] << " ";
		}
		cout << endl;
	}
}

void CMy2DArray::DFS(int x, int y)
{
	// 방문하지 않은 경우
	if ((x >= 0 && x < sizeX) && (y >= 0 && y < sizeY) && (VisitedBlock[x][y] == 0))
	{
		// 방문하였음을 저장한다.
		VisitedBlock[x][y] = 1;

		if (AptBlock[x][y] == 0)
		{
			return;
		}

		//
		BlockCount++;

		// 동 서 남 북
		DFS((x + dx[0]), (y + dy[0]));
		DFS((x + dx[1]), (y + dy[1]));
		DFS((x + dx[2]), (y + dy[2]));
		DFS((x + dx[3]), (y + dy[3]));
	}
}

void CMy2DArray::checkAllBlock()
{
	for (int i = 0; i < sizeX; i++)
	{
		for (int j = 0; j < sizeY; j++)
		{
			BlockCount = 0;
			DFS(i, j);
			if (BlockCount != 0)
			{
				InsertBlockHouseCountArray(BlockCount);
			
			}
		}
	}
}

void CMy2DArray::InsertBlockHouseCountArray(int blockCount)
{
	BlockHouseCountArray[BlockHouseCountArrayLength] = blockCount;
	BlockHouseCountArrayLength++;
	BlockTotalCount++;
}

void CMy2DArray::PrintBlockHouseCountArray()
{
	sort(BlockHouseCountArray, BlockHouseCountArray + BlockHouseCountArrayLength);


	cout << BlockTotalCount << endl;
	for (int i = 0; i < BlockHouseCountArrayLength; i++)
	{
		cout << BlockHouseCountArray[i] << endl;
	}
}

int main()
{
	int blockSize;
	cin >> blockSize;
	CMy2DArray *cMy2DArray = new CMy2DArray(blockSize);
	cMy2DArray->keyBoardInputFillArray();
	cMy2DArray->checkAllBlock();
	cMy2DArray->PrintBlockHouseCountArray();
	return 0;
}

 

입력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

결과

3
7
8
9

 

통과했습니다.

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

---