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 | 색종이(초) > 문제은행
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 첫째 줄에
www.jungol.co.kr
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 | 색종이(중) > 문제은행
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다
www.jungol.co.kr