[C++] 5월 9일 코딩 테스트 수업

#pragma once

#include <iostream>
#include <list>

class C_ISLAND
{
private:
	struct S_NODE
	{
		int nType;
		std::list<S_NODE*> arChild[2];
		std::list<S_NODE*>::iterator iterNodeList; // 일회성
		bool bVisit;
	};

private:
	static int m_arData[10][10];
	S_NODE m_arNode[10][10];
	std::list<S_NODE*> m_listNode;
	std::list<std::list<S_NODE*>*> m_listIsland[2];

private:
	void LinkedNode();
	bool findType(int nY, int nX, int *pType);
	void makeLand();
	void nodeGroup(int nType, S_NODE* pNode, std::list<S_NODE*>& listGroup);

public:
	C_ISLAND() = default;
	void makeNode();
	void print();
	void find();
};

 

#include "island.h"


int C_ISLAND::m_arData[10][10]
{
	{1,1,1,0,0,0,0,1,1,1},
	{1,1,1,1,0,0,0,0,1,1},
	{1,0,1,1,0,0,0,0,1,1},
	{0,0,1,1,1,0,0,0,0,1},
	{0,0,0,1,0,0,0,0,0,1},
	{0,0,0,0,0,0,0,0,0,1},
	{0,0,0,0,0,0,0,0,0,0},
	{0,0,0,0,1,1,0,0,0,0},
	{0,0,0,0,1,1,1,0,0,0},
	{0,0,0,0,0,0,0,0,0,0},
};

//child 연결하는거 여기다 할꺼임
void C_ISLAND::LinkedNode()
{
	int arWay[4][2]{ {-1,0}, {0,1}, {1, 0}, {0, -1} }; // 상하 좌우, X,Y

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			for (int k = 0; k < 4; k++)
			{
				m_arNode[i][j].nType = m_arData[i][j];
				int nType{};
				int nChildY = i + arWay[k][0];
				int nChildX = j + arWay[k][1];
				if(findType(nChildY, nChildX, &nType))
				{
					m_arNode[i][j].arChild[nType].push_back(&m_arNode[nChildY][nChildX]);
				}
			}
			m_listNode.push_back(&m_arNode[i][j]);
			auto iter = m_listNode.end();
			iter--;
			(*iter)->iterNodeList = iter;
		}
	}
}

bool C_ISLAND::findType(int nY, int nX, int* pType)
{
	if (nY < 0 || nX < 0 || nY >= 10 || nX >= 10)
		return false;

	*pType = m_arData[nY][nX];
	return true;
}

void C_ISLAND::makeLand()
{
	while (!m_listNode.empty())
	{
		std::list<S_NODE*>* pListGroup = new std::list<S_NODE*>{};
		S_NODE* pNode = *m_listNode.begin();
		nodeGroup(pNode->nType, pNode, *pListGroup);
		m_listIsland[pNode->nType].push_back(pListGroup);
	}

}

void C_ISLAND::nodeGroup(int nType, S_NODE* pNode, std::list<S_NODE*>& listGroup)
{
	if (pNode->iterNodeList == m_listNode.end())
		return;

	if(!pNode->arChild[0].empty())
		listGroup.push_back(pNode);

	m_listNode.erase(pNode->iterNodeList);
	pNode->iterNodeList = m_listNode.end(); // 방문 여부 마킹, end 지워달라하면 원래는 터진다고 하는데 흠


	for (S_NODE* pChild : pNode->arChild[nType])
	{
		nodeGroup(nType, pChild, listGroup);
	}
}

void C_ISLAND::makeNode()
{
	LinkedNode();
	makeLand();
}

void C_ISLAND::print()
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			printf("%d ",m_arData[i][j]);
		}
		printf("\n");
	}
}

// 원래는 bool형 따로 자료구조를 사용해야함 -> 
void C_ISLAND::find()
{
	std::list < S_NODE*>* pLand = *m_listIsland[1].begin();
	std::list<S_NODE*> que{};

	for (S_NODE* pNode : *pLand)
	{
		pNode->bVisit = true;
		que.push_back(pNode);
	}

	while (!que.empty())
	{
		int nSize = (int)que.size();

		for (int i = 0; i < nSize; i++)
		{
			// 땅인데 방문한적 없으면 종료 
			S_NODE* pNode = *que.begin();
			que.pop_front();

			for (S_NODE* pChild : pNode->arChild[0])
			{
				if (!pChild->bVisit)
				{
					que.push_back(pChild);
					pChild->bVisit = true;
				}
			}
		}
		static int nDepth = 0;
		printf("깊이 : %d\n ", nDepth);
		nDepth++;
	}
}

 

#include <iostream>

#include "island.h"

int main()
{
	C_ISLAND cIsland{};

	cIsland.makeNode();
	cIsland.print();
	cIsland.find();
}