[C언어] 3108. 로고

정답률을 낮춘 장본인!!!!지역변수로 배열을 크게 잡으면 콘솔이 죽어버리는 것도 몰라서..확인도 안 해보고 그냥 제출한 것도 있고....디버깅 하는게 귀찮아서..대충대충 제출해서 이런것이야...ㅋㅋㅋ 어렵게 생각하면 어렵고 쉽다면 쉬운 문제였다!!

배열에 사각형을 그려준 후, 단지에 번호 붙이기 또는 섬의 개수 같은 BFS 문제와 같이 연결되어 있는 사각형의 개수들의 집합만 구해주면 된다!!그리고 집합의 개수 -1이 정답!!집합의 개수가 아닌 펜을 땐 횟수가 정답이니까!!! 배열에 그림을 그려줄 때는 좌표의 *2배 만큼의 길이로 구해주어여 한다. 이유는 아래 그림을 참조하도록!

좌표의 *2의 길이로 안 해주면 아래와 같이 겹치지 않는 사각형임에도 겹쳐서 그려지게 된다!!

따라서 아래와 같이 좌표의 *2배만큼!!

#include <stdio.h>
 
typedef struct
{
    int y, x;
}point;
 
int N;
int arr[1001][4];
int map[2010][2010];
int visit[2010][2010];
int count;
point Q[2000 * 2000] = { 0, };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int Q_Front = -1, Q_Back = -1;
int CheckBound(int y, int x)
{
    if (y < 0 || x < 0 || x>2000 || y>2000)
        return 0;
 
    return 1;
}
 
void Draw(int x1, int y1, int x2, int y2)
{
    int len = (x2 - x1) < 0 ? -1 * (x2 - x1) : (x2 - x1);
    int Flag = (x2 - x1) < 0 ? -1 : 1;
    for (int i = 0; i <= 2 * len; i++)//가로
    {
        map[1000 - y1 * 2][1000 + x1 * 2 + Flag*i] = 1;
        map[1000 - y2 * 2][1000 + x1 * 2 + Flag*i] = 1;
    }
    len = (y2 - y1) < 0 ? -1 * (y2 - y1) : (y2 - y1);
    Flag = (y2 - y1) < 0? -1 : 1;
    for (int i = 0; i <= 2 * len; i++)//세로
    {
        map[1000 - y1 * 2 - Flag*i][1000 + x1 * 2] = 1;
        map[1000 - y1 * 2 - Flag*i][1000 + x2 * 2] = 1;
    }
 
    return;
}
 
int main()
{
    Q_Front = -1; Q_Back = -1;
    scanf("%d", &N);
    count = 0;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d %d %d", &arr[i][0], &arr[i][1], &arr[i][2], &arr[i][3]);
    }
 
    map[1000][1000] = 1;
 
    for (int i = 1; i <= N; i++)
    {
        Draw(arr[i][0], arr[i][1], arr[i][2], arr[i][3]);
    }
 
    for (int i = 0; i < 2001; i++)
    {
        for (int j = 0; j < 2001; j++)
        {
            if (map[i][j] == 1 && visit[i][j] == 0)
            {
                count++;
                Q[++Q_Back].y = i;
                Q[Q_Back].x = j;
                visit[i][j] = 1;
 
                while (Q_Front != Q_Back)
                {
                    int y = Q[++Q_Front].y;
                    int x = Q[Q_Front].x;
 
                    for (int a = 0; a < 4; a++)
                    {
                        int yy = y + dy[a];
                        int xx = x + dx[a];
 
                        if (!CheckBound(yy, xx))
                            continue;
 
                        if (map[yy][xx] == 1 && visit[yy][xx] == 0)
                        {
                            Q[++Q_Back].y = yy;
                            Q[Q_Back].x = xx;
                            visit[yy][xx] = 1;
                        }
                    }
                }
            }
        }
    }
 
    printf("%d\n",count - 1);
 
    return 0;
}