JUNGOL 실력키우기 여러가지 - 색종이(초) | 색종이(중)

기초 다지기에서 배운 내용을 응용하여 문제를 해결해야 하는 실력 키우기입니다.

실력 키우기는 비슷한 문제 유형별로 묶어서 풀어보겠습니다.

 

이번 포스팅에서는 여러가지의 색종이 시리즈를 풀어보겠습니다.

---

1438 : 색종이(초)

 

이 문제는 가장 단순한 것이 정답일 수 있다는 것을 잘 보여주는 듯한 문제인 듯 합니다.

단순하게 100 x 100 크기의 bool형 배열을 만들고 최초로 체크될 때 넓이에 1을 추가하는 방식을 사용하면 입력된 위치를 따로 저장할 필요 없이 쉽게 넓이를 알아낼 수 있습니다.

 

#include <iostream>

using namespace std;

bool area[101][101];

int main(void)
{
	int n;
	cin >> n;

	int x, y;
	int totalArea{ 0 };
	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;
		for (int j = y; j < y + 10; ++j)
		{
			for (int k = x; k < x + 10; ++k)
			{
				if (!area[j][k])
				{
					area[j][k] = true;
					totalArea++;
				}
			}
		}
	}

	cout << totalArea << endl;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=712&sca=2060

JUNGOL | 색종이(초) > 문제은행

 

1671 : 색종이(중)

 

이 문제는 기본적으로 시작 값부터 끝 값까지를 선을 긋고 그 사이의 간격을 채운다는 시점에서 생각하는 쪽이 문제 이해가 더 쉽습니다.

 

만약 0 0 이 들어올 때 0~ 9까지의 칸을 채운다고 생각한다면 다음과 같은 문제가 발생합니다.

 

차라리 0~10까지 선을 긋고 그 사이의 간격을 계산하는 경우에 더 자연스럽게 처리할 수 있게 됩니다.

 

여기까지 처리한 코드는 다음과 같습니다.

 

#include <iostream>

using namespace std;

bool IsEdge(int x, int y, int px, int py);
bool IsVertex(int x, int y, int px, int py);

enum areaType{
	empty = 0,
	face,
	edge
};

areaType area[102][102]{};

int main(void)
{
	int n;
	cin >> n;

	int x, y;
	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;
		for (int j = y; j <= y + 10; ++j)
		{
			for (int k = x; k <= x + 10; ++k)
			{
				if (IsEdge(x, y, k, j))
				{
					if(area[j][k] != areaType::face)
					{
						area[j][k] = areaType::edge;
					}
				}
				else
				{
					area[j][k] = areaType::face;
				}
			}
		}
	}

	for (int v = 0; v < 101; ++v)
	{
		for (int w = 0; w < 101; ++w)
		{
			if (area[v][w] == areaType::edge)
			{
				cout << "■";
			}
			else if (area[v][w] == areaType::face)
			{
				cout << "□";
			}
			else
			{
				cout << "  ";
			}
		}
		cout << endl;
	}

	int totalArea{ 0 };
	for (int i = 0; i < 101; ++i)
	{
		for (int j = 0; j < 101; ++j)
		{
			if (area[i][j] == areaType::edge)
			{
				if (area[i + 1][j] == areaType::edge)
				{
					totalArea++;
				}
				if (area[i][j + 1] == areaType::edge)
				{
					totalArea++;
				}
			}
		}
	}

	cout << totalArea << endl;
}

bool IsEdge(int x, int y, int px, int py)
{
	if (px == x) return true;
	if (px == x + 10) return true;
	if (py == y) return true;
	if (py == y + 10) return true;
	return false;
}

bool IsVertex(int x, int y, int px, int py)
{
	if (px == x && py == y) return true;
	if (px == x + 10 && py == y) return true;
	if (px == x && py == y + 10) return true;
	if (px == x + 10 && py == y + 10) return true;
	return false;
}

 

그런데 여기에서 어색한 부분을 찾을 수 있는데, 바로 두 상자가 겹치면서 중간에 선이 남게 되는 것 입니다.

 

이 문제를 해결하기 위해 모서리를 넣을 때 이미 모서리인 경우 면으로 체크하도록 변경하겠습니다.

 

	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;
		for (int j = y; j <= y + 10; ++j)
		{
			for (int k = x; k <= x + 10; ++k)
			{
				if (IsEdge(x, y, k, j))
				{
					// 코드 추가
					if (area[j][k] == areaType::edge)
					{
						area[j][k] = areaType::face;
					}
					if(area[j][k] != areaType::face)
					{
						area[j][k] = areaType::edge;
					}
				}
				else
				{
					area[j][k] = areaType::face;
				}
			}
		}
	}

 

이 코드로 실행한 결과는 다음과 같습니다.

 

이것을 위해 모서리를 체크하는 작업을 추가 처리해주도록 하겠습니다.

모서리는 현 위치가 면 일때, 상하좌우에 두개 이상의 모서리가 존재하고 대각선에는 모서리가 없는 경우인 것 같습니다.

추가한 코드는 다음과 같습니다.

 

int main(void)
{
	// ... 중략
    
	for (int i = 0; i <= 100; ++i)
	{
		for (int j = 0; j <= 100; ++j)
		{
			if (IsVertex(j, i))
			{
				area[i][j] = areaType::edge;
			}
		}
	}

	// ... 후략
}

// ...

bool IsVertex(int px, int py)
{
	if (area[py][px] != areaType::face)
		return false;

	// 대각선 체크
	if (px > 0 && py > 0 && area[py - 1][px - 1] == areaType::edge)
		return false;
	if (px > 0 && py < 100 && area[py + 1][px - 1] == areaType::edge)
		return false;
	if (px < 100 && py > 0 && area[py - 1][px + 1] == areaType::edge)
		return false;
	if (px < 100 && py < 100 && area[py + 1][px + 1] == areaType::edge)
		return false;

	// 상하좌우 체크
	int crossCount{ 0 };
	if (px > 0 && area[py][px - 1] == areaType::edge)
		crossCount++;
	if (px < 100 && area[py][px + 1] == areaType::edge)
		crossCount++;
	if (py > 0 && area[py - 1][px] == areaType::edge)
		crossCount++;
	if (py < 100 && area[py + 1][px] == areaType::edge)
		crossCount++;

	return crossCount >= 2;
}

 

이 코드의 실행 결과는 다음과 같습니다.

 

실행결과는 다음과 같습니다.

 

실패했습니다. 실패한 경우를 출력하니 신경쓰이는 부분이 보입니다.

 

정확하게 확인하기 위해 사각형 하나하나가 보이도록 출력했습니다.

아래쪽 사각형은 정상출력된 상태였습니다. 결국 문제는 상단의 두 사각형 처럼 깊게 곂치는 경우인 것 같습니다.

 

이번에는 생각을 반대로 바꿔서 면 기준으로 처리해봤습니다. 기본적으로 이전 상태처럼 모서리를 살려둔 상태에서 모서리의 사방의 두개이상이 면이고 대각선 방향이 비어있지 않으면 해당 모서리도 면인 것으로 처리했습니다.

 

코드는 다음과 같으며 제거한 코드는 주석으로 처리했습니다.

 

#include <iostream>

using namespace std;

bool IsEdge(int x, int y, int px, int py);
//bool IsVertex(int px, int py);
bool IsFace(int px, int py);

enum areaType{
	empty = 0,
	face,
	edge
};

areaType area[102][102]{};

int main(void)
{
	int n;
	cin >> n;

	int x, y;
	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;
		for (int j = y; j <= y + 10; ++j)
		{
			for (int k = x; k <= x + 10; ++k)
			{
				if (IsEdge(x, y, k, j))
				{
					//if (area[j][k] == areaType::edge)
					//{
					//	area[j][k] = areaType::face;
					//}
					if(area[j][k] != areaType::face)
					{
						area[j][k] = areaType::edge;
					}
				}
				else
				{
					area[j][k] = areaType::face;
				}
			}
		}
	}

	//for (int i = 0; i <= 100; ++i)
	//{
	//	for (int j = 0; j <= 100; ++j)
	//	{
	//		if (IsVertex(j, i))
	//		{
	//			area[i][j] = areaType::edge;
	//		}
	//	}
	//}
	for (int i = 0; i <= 100; ++i)
	{
		for (int j = 0; j <= 100; ++j)
		{
			if (IsFace(j, i))
			{
				area[i][j] = areaType::face;
			}
		}
	}

	int totalArea{ 0 };
	for (int i = 0; i <= 100; ++i)
	{
		for (int j = 0; j <= 100; ++j)
		{
			if (area[i][j] == areaType::edge)
			{
				if (area[i + 1][j] == areaType::edge)
				{
					totalArea++;
				}
				if (area[i][j + 1] == areaType::edge)
				{
					totalArea++;
				}
			}
		}
	}

	cout << totalArea << endl;
}

bool IsEdge(int x, int y, int px, int py)
{
	if (px == x) return true;
	if (px == x + 10) return true;
	if (py == y) return true;
	if (py == y + 10) return true;
	return false;
}

//bool IsVertex(int px, int py)
//{
//	if (area[py][px] != areaType::face)
//		return false;
//
//	// 대각선 체크
//	if (px > 0 && py > 0 && area[py - 1][px - 1] == areaType::edge)
//		return false;
//	if (px > 0 && py < 100 && area[py + 1][px - 1] == areaType::edge)
//		return false;
//	if (px < 100 && py > 0 && area[py - 1][px + 1] == areaType::edge)
//		return false;
//	if (px < 100 && py < 100 && area[py + 1][px + 1] == areaType::edge)
//		return false;
//
//	// 상하좌우 체크
//	int crossCount{ 0 };
//	if (px > 0 && area[py][px - 1] == areaType::edge)
//		crossCount++;
//	if (px < 100 && area[py][px + 1] == areaType::edge)
//		crossCount++;
//	if (py > 0 && area[py - 1][px] == areaType::edge)
//		crossCount++;
//	if (py < 100 && area[py + 1][px] == areaType::edge)
//		crossCount++;
//
//	return crossCount >= 2;
//}

bool IsFace(int px, int py)
{
	if (area[py][px] != areaType::edge)
		return false;

	// 대각선 체크
	if (px > 0 && py > 0 && area[py - 1][px - 1] == areaType::empty)
		return false;
	if (px > 0 && py < 100 && area[py + 1][px - 1] == areaType::empty)
		return false;
	if (px < 100 && py > 0 && area[py - 1][px + 1] == areaType::empty)
		return false;
	if (px < 100 && py < 100 && area[py + 1][px + 1] == areaType::empty)
		return false;

	// 상하좌우 체크
	int crossCount{ 0 };
	if (px > 0 && area[py][px - 1] == areaType::face)
		crossCount++;
	if (px < 100 && area[py][px + 1] == areaType::face)
		crossCount++;
	if (py > 0 && area[py - 1][px] == areaType::face)
		crossCount++;
	if (py < 100 && area[py + 1][px] == areaType::face)
		crossCount++;

	return crossCount >= 2;
}

 

이 코드의 실행 결과는 다음과 같습니다.

 

모양은 맞는 것 같은데 결과적으로 실패했습니다. 고민을 더 해봐야 할 것 같습니다.

먼저, 모서리를 구분하지 않고 모두 같은 모양으로 출력해보겠습니다.

 

 

이 상황에서 반복문을 돌면서 현재 위치가 면인 경우 상하좌우가 빈 상태일 때 모서리로 판단해보겠습니다.

단, 해당 위치를 기준으로(칸 단위로) 개수를 세기 때문에 다시 면을 체크하는 부분도 시작값 <= 면 < 끝값으로 체크해야 할 것 같습니다.

 

추가적으로 상, 하, 좌, 우를 각각 체크해서 개수를 추가해야 하는데 꼭지점 부근은 두번씩 셀 필요가 있기 때문입니다.

(가령 오른쪽 꼭지점은 상단과 우측에 하나씩 두개의 빈 칸을 가집니다.)

 

#include <iostream>

using namespace std;

int GetEdgeCount(int x, int y);

enum areaType{
	empty = 0,
	face
};

areaType area[100][100]{};

int main(void)
{
	int n;
	cin >> n;

	int x, y;
	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;
		for (int j = y; j < y + 10; ++j)
		{
			for (int k = x; k < x + 10; ++k)
			{
				area[j][k] = areaType::face;
			}
		}
	}

	int totalArea{ 0 };
	for (int i = 0; i < 100; ++i)
	{
		for (int j = 0; j < 100; ++j)
		{
			totalArea += GetEdgeCount(j, i);
		}
	}
	cout << totalArea << endl;
}

int GetEdgeCount(int x, int y)
{
	int count{ 0 };
	if (area[y][x] == areaType::face)
	{
		// Left
		if (x <= 0 || area[y][x - 1] == areaType::empty) count++;

		// Right
		if (x >= 99 || area[y][x + 1] == areaType::empty) count++;

		// Up
		if (y <= 0 || area[y - 1][x] == areaType::empty) count++;

		// Down
		if (y >= 99 || area[y + 1][x] == areaType::empty) count++;
	}
	return count;
}

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=944&sca=2060

JUNGOL | 색종이(중) > 문제은행