[ 백준 3108 ] 로고 (C++)

백준의 로고(3108) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에 접근하기가 굉장히 어려웠던 문제이다. 먼저 입력을 받는 것 부터 차근차근 알아보도록 하자.

   입력으로는 사각형의 양 끝 꼭지점의 좌표 2개가 주어진다.

   그리고 그 좌표의 범위는 -500 ~ 500 이다. 하지만, 우리가 컴퓨터로 배열을 만든다면, 범위는 0부터 가능하다. (-1, -1)같은

   좌표는 표현을 할 수가 없다. 따라서, 입력받는 좌표 값들에 +500 씩을 해서 받아주자.

   그렇게 되면, (-500, -500)을 입력받는다고 하더라도, (0, 0)이 될테니까 !

   여기서 입력받는 것이 끝난다면 참 좋을텐데, 아래의 그림을 보고 잘못된 점을 한번 찾아보자.

  

   문제에서 입력으로 주어진 예제입력 1에서, 위의 3개의 좌표를 가져와서 배열에 입력한 것 처럼 직접 그려본 것이다.

   (표현은 (1, 1)로 했지만 500씩 +된 값이라고 생각하자 !)

   위에서 보면, 3개의 사각형 모두 겹친다는 것을 알 수 있다. 그런데 잘 생각해보면,

   (1, 1), (4, 4)로 표현된 파랑색 사각형과, (3, 3), (6, 6)으로 표현된 초록색 사각형은 겹치는게 맞다. 그런데,

   초록색과 빨강색 사각형을 잘 봐보자. 빨강색의 좌표는 (4, 4) 와 (5, 5)이다. 모눈종이에 우리가 직접 그림을 그려본다면

   초록색과 빨강색 사각형은 사이에 간격이 있어서 겹치지 않는 다는 것을 알 수 있다.

  

   위의 그림처럼, 직접 그려본다면 저렇게 겹치지 않는 사각형 2개로 그려진다.(그림이 굉장히 미숙하지만 초록,빨강 사각형을

   그려본 것이다)

   하지만, 우리가 입력받은 대로 배열에 표현해 버린다면 저렇게 겹쳐지는 현상이 발생한다. 그렇다면 여기서, 저렇게 겹쳐지는게

   왜 문제가 되는지 알고 넘어가자.

   이 문제를 한마디로 요약해서 설명하자면 주어진 사각형들을 한붓그리기 몇번으로 그릴 수 있냐 ?! 를 묻는 문제라고 생각하면

   된다. 즉, 겹쳐진 사각형들은 한붓그리기로 펜을 들어올리지 않고 연속해서 그릴 수 있지만, 겹쳐지지 않은 사각형들은

   펜을 떼고, 다시 그 좌표에서 새로운 한붓그리기를 시작해야 된다는 것이다. 우리가 출력해야 될 답은, 붓을 몇 번 들어올렸는지

   를 출력해야 하는 것이다. 따라서, 위의그림처럼 겹쳐지지 않는 사각형을 겹쳐진 것처럼 입력해 버린다면 당연하게도 오답을

   출력하게 될 것이다. 그렇다면, 실제 모눈종이처럼 간격을 넓히려면 어떻게 해야 할까??

   좌표들의 값을 x2씩 해버리면 된다. 즉, 입력받는 좌표들의 값들을 +500씩 하고, x2 까지 해버린다면, 우리가 원하는 이쁜 그림을

   입력으로 받아낼 수 있다.

  

   그렇다면 주어진 맵의 최대크기에 대해서 생각해보자. (500, 500)으로 좌표가 입력된다면, 위에서 말했듯이, (2000, 2000)을

   입력받는 셈이 될 것이다.((500 + 500) x 2 , (500 + 500) x 2) 이기 때문이다.

   즉, 입력받는 맵을 MAP[][]으로 입력받되, 최대크기를 MAP[2001][2001]로 설정해주자 !

  

2) 본격적으로 문제 풀이에 들어가보자. 우리는 1)에서 좌표를 어떻게 입력받을 지를 결정했고, 아직 입력도 받지 않았다.

   입력받을 값들을 설정했을 뿐이다. 사각형들을 맵에서 1로 표현해주자. 아래와 같이 !

    for (int i = 0; i < N; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        x1 = (x1 + 500) * 2;
        y1 = (y1 + 500) * 2;
        x2 = (x2 + 500) * 2;
        y2 = (y2 + 500) * 2;

        for (int i = x1; i <= x2; i++) { MAP[y1][i] = 1;  MAP[y2][i] = 1;  }
        for (int i = y1; i <= y2; i++) { MAP[i][x1] = 1;  MAP[i][x2] = 1;  }
    }

    

   사각형들을 1로 표현해주었다. 이제, (0, 0)에 있는 거북이로 직사각형을 그리는데, 사실, 거북이를 조종하는 명령어

   들을 크게 신경쓰지 않아도 된다. 결과적으로, 상하좌우로 인접한 곳으로 거북이가 움직일 수 있다는 것을 의미하기 때문이다.

   따라서, 이 문제는 "모든 좌표를 돌아보면서, 사각형이 있으면서, 아직 방문하지 않은 사각형이라면 탐색" 을 해주면 된다.

   여기서 "탐색"이라 함은, BFS/DFS같은 함수를 호출하는 것을 의미한다. 특정 좌표에서 시작해서 거북이를 들어올리지 않고
   그릴 수 있는 사각형이라면 모두 그려주고 더 이상 그릴 수 없을 때 함수를 종료하는 것이다.

   즉, BFS / DFS함수가 호출되는 횟수가 거북이를 들어올리는 명령인 PU명령을 실행한 횟수가 될 것이다.

   본인은, 방문한 사각형을 표시해주기 위해서 '1'로 표현된 사각형을, 탐색 후에는 '2'로 바꿔주었다.

  

3) 이제 제출하면 아마 틀릴 것이다. 본인도 이 부분에서 상당히 애를 먹었는데, 거북이가 처음에 (0, 0)위치에 연필을 내리고

   있다는 말이 문제에서 주어진다. 우리는 문제를 너무나도 자연스럽게, 연필이 들어올려져 있는 채로 탐색을 한 것 처럼

   문제를 풀어놓았다. 우리의 풀이를 다시한번 봐보면, 사각형이 있을 때, 연필을 내려서 탐색을 하고 ,더 이상 탐색할 수

   없다면, 다시 연필을 들어올려라 ! 라는 식으로 풀이가 되어있다.

   쉽게 얘기해서, 거북이가 처음에 있는 위치인 (0, 0) 에서가 아닌, 우리의 입력방식대로 바꾼 (1000, 1000) 에도 사각형이

   존재한다면, 연필을 들어올리지 않고 바로 사각형을 그릴 수가 있다. 즉, MAP[1000][1000] = 2 라면, 연필을 들어올린 횟수를

   1회 빼줘야 한다는 점을 생각해 줘야 한다 !

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 2001
using namespace std;
 
int N;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
 
        x1 = (x1 + 500) * 2;
        y1 = (y1 + 500) * 2;
        x2 = (x2 + 500) * 2;
        y2 = (y2 + 500) * 2;
 
        for (int i = x1; i <= x2; i++)
        {
            MAP[y1][i] = 1;
            MAP[y2][i] = 1;
        }
        for (int i = y1; i <= y2; i++)
        {
            MAP[i][x1] = 1;
            MAP[i][x2] = 1;
        }
    }
}
 
void DFS(int y, int x)
{
    if (y < 0 || x < 0 || x >= MAX || y >= MAX) return;
    if (MAP[y][x] == 2 || MAP[y][x] == 0) return;
 
    MAP[y][x] = 2;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        DFS(ny, nx);
    }
}
 
void Solution()
{
    int Pu_Cnt;
 
    Pu_Cnt = 0;
 
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (MAP[i][j] == 1)
            {
                DFS(i, j);
                Pu_Cnt++;
            }
        }
    }
 
    if (MAP[1000][1000] == 2) Pu_Cnt--;
    cout << Pu_Cnt << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}