3108번

3108번 - 로고

나는 이 문제를 연결요소의 갯수를 구하는 문제로 접근했다.

결국 DFS를 통해서 한붓그리기가 가능하면 거북이가 붓을 뗄 필요가 없기 때문이다.

그래서 처음에 makeGraph 함수를 통해서 각 점들을 정점으로 간선들을 모두 연결해줬다.

이 과정에서 음수 값들을 제거하기 위해 모든 점들에 500을 더해줬다.

그래서 모든 점을 DFS 로 순회해서 연결요소의 갯수를 풀면 된다.

단 주의해야 할 점은 , 거북이가 시작점에 있느냐 있지 않느냐의 문제이다.. 이 부분에서 계속 헤맸다..

처음에 N==1 일 때 문제인줄 알았지만 그것도 아니었고.. 그냥 거북이의 시작점에서 처음에 시작할 수 있는가 없는가였다.

거북이의 시작점에서 시작할 수 있다면, 연결요소의 갯수에서 하나를 빼야하기 때문이다. 연필을 들어올릴 필요가 없기 때문에...

그래서 마지막에 if문을 통해서 시작점에서 시작할 수 있을 경우에는 답에서 1을 빼줬다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
vector<pair<int,int>> v[1001][1001];
bool visited[1001][1001];
void makeGraph(int X, int Y, int toX, int toY)
{
    for (int i = X; i <= toX; i++)
    {
        for (int j = Y; j <= toY; j++)
        {
            if ((i == X || i==toX) && j<toY)
            {
                v[i][j].push_back(make_pair(i, j + 1));
                v[i][j + 1].push_back(make_pair(i, j));
            }
 
            if ((j == Y || j == toY) && i < toX)
            {
                v[i][j].push_back(make_pair(i + 1, j));
                v[i + 1][j].push_back(make_pair(i, j));
            }
        }
    }
}
void dfs(int x, int y)
{
    visited[x][y] = true;
 
    for (int i = 0; i < v[x][y].size(); i++)
    {
        int nx = v[x][y][i].first;
        int ny = v[x][y][i].second;
 
        if (!visited[nx][ny])
        {
            dfs(nx, ny);
        }
    }
 
    return;
}
int main()
{
    int N, ans = 0;
    bool needMove = true;
    int firstX = 0 + 500;
    int firstY = 0 + 500;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int X, Y, toX, toY;
        cin >> X >> Y >> toX >> toY;
 
        makeGraph(X + 500, Y + 500, toX + 500, toY + 500);
    }
 
    for (int i = 0; i <= 1000; i++)
    {
        for (int j = 0; j <= 1000; j++)
        {
            if (!visited[i][j] && v[i][j].size() != 0)
            {
                ans += 1;
                dfs(i, j);
            }
        }
    }
 
    //시작점에서 출발할 수 있는 경우
    if (v[firstX][firstY].size() != 0)
    {
        ans -= 1;
    }
 
 
    cout << ans << endl;
 
 
    return 0;
}