JUNGOL 실력키우기 1671 : 색종이(중)

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.

 

예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.

 

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 
색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고,
 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 
색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

 

첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.

[Copy] 4 3 7 5 2 15 7 13 14

[Copy] 96

---

이번 문제는 지난번 색종이(초)에 이은 큰 도화지에 색종이를 붙이는 문제인데요,

이번에는 넓이가 아니라 둘레를 구하는 것으로 약간 변형되었습니다.

먼저 문제에서 필요한 변수들을 살펴보면,

 가로, 세로크기가 100인 도화지가 있다 -> 100 * 100 배열

  첫째 줄에 색종이의 수가 주어진다. -> 수를 저장할 정수형 변수

  색종이를 붙인 위치는 두 개의 자연수로 주어지는데 - > 입력되는 변수는 x, y

그리고 이제 실제로 알고리즘에 대한 생각을 해 봅시다.

둘레를 살펴보면 둘레는 상, 하, 좌, 우에 적어도 하나의 빈 공간이 존재합니다.

또, 꼭지점 부분은 그 중 두개에 속하게 됩니다.

즉, 둘레는 상, 하, 좌, 우에 빈공간이 존재할 때마다 둘레를 증가시켜 구하면됩니다.

#include <iostream>
 
using namespace std;
 
struct POINT{
    int x, y;
};
 
istream& operator>>(istream& is, POINT& p)
{
    is >> p.x >> p.y;
    return is;
}
 
enum Color { WHITE, BLACK };
 
void Paint(int board[][100], POINT& coord);
int CheckCircumference(int board[][100]);
bool IsBlack(int col);
bool CheckLeft(int board[][100], int x, int y);
bool CheckRight(int board[][100], int x, int y);
bool CheckUp(int board[][100], int x, int y);
bool CheckDown(int board[][100], int x, int y);
int EdgeCnt(int board[][100], int x, int y);
 
int main(void) {
    int board[100][100]{};    // 흰 도화지
    int n;    // 입력될 색종이의 개수
    POINT coord;    // 입력될 색종이의 좌하단 위치
 
    cin >> n;
 
    // 각 색종이의 좌표를 입력받아 칠한다.
    for (int i = 0; i < n; ++i)
    {
        cin >> coord;
        Paint(board, coord);
    }
 
    // 결과 출력
    cout << CheckCircumference(board) << endl;
}
 
// 색종이 위치를 칠해주는 함수
void Paint(int board[][100], POINT& coord)
{
    for (int y = coord.y; y < coord.y + 10; ++y)
    {
        for (int x = coord.x; x < coord.x + 10; ++x)
        {
            board[y][x] = Color::BLACK;
        }
    }
}
 
// 색종이의 둘레를 리턴하는 함수
int CheckCircumference(int board[][100])
{
    int Circumference = 0;
 
    for (int y = 0; y < 100; ++y)
    {
        for (int x = 0; x < 100; ++x)
        {
            if (!IsBlack(board[y][x])) continue;
            Circumference += EdgeCnt(board, x, y);
        }
    }
 
    return Circumference;
}
 
// 현재 위치가 색종이 영역인지 검사
bool IsBlack(int col)
{
    return col == Color::BLACK;
}
 
// 왼쪽이 비었는지 확인
bool CheckLeft(int board[][100], int x, int y)
{
    if (x == 0) return true;
    if (board[y][x - 1] == Color::WHITE) return true;
    return false;
}
 
// 오른쪽이 비었는지 확인
bool CheckRight(int board[][100], int x, int y)
{
    if (x  == 99) return true;
    if (board[y][x + 1] == Color::WHITE) return true;
    return false;
}
 
// 위쪽이 비었는지 확인
bool CheckUp(int board[][100], int x, int y)
{
    if (y == 99) return true;
    if (board[y + 1][x] == Color::WHITE) return true;
    return false;
}
 
// 아래쪽이 비었는지 확인
bool CheckDown(int board[][100], int x, int y)
{
    if (y == 0) return true;
    if (board[y - 1][x] == Color::WHITE) return true;
    return false;
}
 
// 현재 지점이 몇 개의 모서리에 속해있는지 파악하여 리턴한다.
int EdgeCnt(int board[][100], int x, int y)
{
    int cnt = 0;
    // 사방 중 하나라도 도화지면 혹은 범위를 벗어나는 경우 모서리다.
    if (CheckLeft(board, x, y)) cnt++;
    if (CheckRight(board, x, y)) cnt++;
    if (CheckUp(board, x, y)) cnt++;
    if (CheckDown(board, x, y)) cnt++;
    return cnt;
}

JUNGOL) 문제은행) 실력키우기) 색종이(중)