백준 1012번 유기농 배추 C++ 구현해보기

---

```

백준 1012번 유기농 배추 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 1012번 풀이

---

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

1012번: 유기농 배추

 

 

 

백준 1012번 유기농 배추는

난이도 중하 등급의 문제로서

 

테스트 케이스 입력후

테스트 케이스만큼 2D 지도크기를 입력 받은 다음

0으로 표시된 지도에 1로 배추의 위치를 표기하고

이어진 배추만큼 지렁이의 갯수를 세주면 되는 문제입니다.

 

---

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

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

---

 

 

일단 테스트 케이스만큼 객체를 만들고

진행을 하였습니다.

int main()
{

	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	int testCaseNum;
	std::cin >> testCaseNum;
	std::cin.ignore();

	for (int i = 0; i < testCaseNum; i++)
	{
		CCabbageMap* cCabbageMap = new CCabbageMap();
		cCabbageMap->getUserInput();
		cCabbageMap->findMaggotNum();
		cCabbageMap->printMaggotNum();
		//cCabbageMap->printCabbageMap();
		delete cCabbageMap;
	}
}

유저 입력을 받아서

배추 지도

방문한 배추지도

그리고

배추지도에 표기되는 좌표 값들을 넣어주었고

	/* 입력 */
	void getUserInput()
	{
		inputFieldSizeAndCabbageNo();
		makeCabbageField();
		makeCabbageFieldMap();
		plotCabbages();
	}

	void inputFieldSizeAndCabbageNo()
	{
		std::string tempStr;
		std::getline(std::cin, tempStr);
		std::stringstream ss(tempStr);
		ss >> colX;
		ss >> rowY;
		ss >> cabbageNum;
	}

	void makeCabbageField()
	{
		for (int i = 0; i < rowY; i++) 
		{ 
			std::vector<int> tempVec; 
			for (int j = 0; j < colX; j++) 
			{ 
				tempVec.push_back(0); 
			} 
			cabbageMap.push_back(tempVec);
		}
	}

	void makeCabbageFieldMap()
	{
		for (int i = 0; i < rowY; i++)
		{
			std::vector<int> tempVec;
			for (int j = 0; j < colX; j++)
			{
				tempVec.push_back(0);
			}
			visitedCabbageMap.push_back(tempVec);
		}
	}

	void plotCabbages()
	{
		for (int i = 0; i < cabbageNum; i++)
		{
			std::string tempStr;
			std::getline(std::cin, tempStr);
			std::stringstream ss(tempStr);
			int x;
			int y;

			ss >> x;
			ss >> y;

			cabbageMap[y][x] = 1;
		}


	}

 

각 좌표에 깊이 우선 탐색을 해서

방문하였거나

배추가 없는 좌표는 리턴하고

좌표가 있는 방문하지 않은 배추를 동서남북으로 재귀적으로 찾아서

연결된 배추들을 찾아주고

 

그러한 방법으로

각 배추 블럭에 들어갈

지렁이 수를 카운팅 했습니다.

 

	void findMaggotNum()
	{

		for (int i = 0; i < rowY; i++)
		{
			for (int j = 0; j < colX; j++)
			{
				blockCount = 0;
				DFS(i, j);
				if (blockCount != 0)
				{
					maggotNum++;
				}
			}
		}
	}

	void DFS(int y, int x)
	{

		if ((x >= 0 && x < colX) && (y >= 0 && y < rowY) && (visitedCabbageMap[y][x] == 0))
		{
			// 방문하였음을 저장한다. 
			visitedCabbageMap[y][x] = 1;

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

			blockCount++;

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

 

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>

class CCabbageMap {

private:
	/* 가로 길이 M */
	int32_t colX;
	/* 세로 길이 N */
	int32_t rowY;
	/* 배추 갯수 K */
	int32_t cabbageNum;
	/* 배추 지도 */
	std::vector<std::vector<int>> cabbageMap;
	/* 방문한 위치 표시 지도 */
	std::vector<std::vector<int>> visitedCabbageMap;
	/* 연결된 배추 영역 */
	int32_t blockCount;

	/* 지렁이 수 */
	int32_t maggotNum;

	/* 이동 방향 */
	int dx[4] = { 1,-1,0,0 }; 
	int dy[4] = { 0, 0,1,-1 };

public:

	CCabbageMap()
	{
		blockCount = 0;
		colX = 0;
		rowY = 0;
		cabbageNum = 0;
		maggotNum = 0;
	}

	~CCabbageMap()
	{

	}

	/* 입력 */
	void getUserInput()
	{
		inputFieldSizeAndCabbageNo();
		makeCabbageField();
		makeCabbageFieldMap();
		plotCabbages();
	}

	void inputFieldSizeAndCabbageNo()
	{
		std::string tempStr;
		std::getline(std::cin, tempStr);
		std::stringstream ss(tempStr);
		ss >> colX;
		ss >> rowY;
		ss >> cabbageNum;
	}

	void makeCabbageField()
	{
		for (int i = 0; i < rowY; i++) 
		{ 
			std::vector<int> tempVec; 
			for (int j = 0; j < colX; j++) 
			{ 
				tempVec.push_back(0); 
			} 
			cabbageMap.push_back(tempVec);
		}
	}

	void makeCabbageFieldMap()
	{
		for (int i = 0; i < rowY; i++)
		{
			std::vector<int> tempVec;
			for (int j = 0; j < colX; j++)
			{
				tempVec.push_back(0);
			}
			visitedCabbageMap.push_back(tempVec);
		}
	}

	void plotCabbages()
	{
		for (int i = 0; i < cabbageNum; i++)
		{
			std::string tempStr;
			std::getline(std::cin, tempStr);
			std::stringstream ss(tempStr);
			int x;
			int y;

			ss >> x;
			ss >> y;

			cabbageMap[y][x] = 1;
		}


	}

	void findMaggotNum()
	{

		for (int i = 0; i < rowY; i++)
		{
			for (int j = 0; j < colX; j++)
			{
				blockCount = 0;
				DFS(i, j);
				if (blockCount != 0)
				{
					maggotNum++;
				}
			}
		}
	}

	void DFS(int y, int x)
	{

		if ((x >= 0 && x < colX) && (y >= 0 && y < rowY) && (visitedCabbageMap[y][x] == 0))
		{
			// 방문하였음을 저장한다. 
			visitedCabbageMap[y][x] = 1;

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

			blockCount++;

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

	void printMaggotNum()
	{
		std::cout << maggotNum << "\n";
	}

	void printCabbageMap()
	{
		for (int i = 0; i < rowY; i++)
		{
			for (int j = 0; j < colX; j++)
			{
				std::cout << cabbageMap[i][j];
			}
			std::cout << "\n";
		}
	}

	void printVisitedCabbageMap()
	{
		for (int i = 0; i < rowY; i++)
		{
			for (int j = 0; j < colX; j++)
			{
				std::cout << visitedCabbageMap[i][j];
			}
			std::cout << "\n";
		}
		std::cout << "\n";
		std::cout << "\n";
	}

};



int main()
{

	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);
	int testCaseNum;
	std::cin >> testCaseNum;
	std::cin.ignore();

	for (int i = 0; i < testCaseNum; i++)
	{
		CCabbageMap* cCabbageMap = new CCabbageMap();
		cCabbageMap->getUserInput();
		cCabbageMap->findMaggotNum();
		cCabbageMap->printMaggotNum();
		//cCabbageMap->printCabbageMap();
		delete cCabbageMap;
	}
}

 

읽어주셔서 감사합니다

 

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

 

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

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

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

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---