[BFS] 3108번 로고

3108번 로고

 

https://www.acmicpc.net/problem/3108

 

문제

로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.

거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.

제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.

사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.

1. FD x: 거북이를 x만큼 앞으로 전진
2. LT a: 거북이를 반시계 방향으로 a도 만큼 회전
3. RT a: 거북이를 시계 방향으로 a도 만큼 회전
4. PU: 연필을 올린다
5. PD: 연필을 내린다.

축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.

거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 직사각형을 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.

 

입력

첫째 줄에 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

다음 N개의 줄에는 직사각형의 좌표 x1, y1, x2, y2가 주어진다. (−500 ≤ x1 < x2 ≤ 500), (−500 ≤ y1 < y2 ≤ 500) (x1, y1)는 직사각형의 한 꼭짓점 좌표이고, (x2, y2)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.

 

출력

N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.

 

예제 입력

5
1 1 4 4
3 3 6 6
4 4 5 5
5 0 8 3
6 1 7 2

 

예제 출력

2

 

해결방법

BFS 탐색을 통해 한 붓 그리기 를 수행하는 문제이다

 

 

⭐️ 솔루션 ⭐️

이 문제를 처음 보고 명령대로 로봇을 움직이는 완전탐색 문제라고 생각했다

하지만 직접 손으로 직사각형을 그리다가 선이 겹치는 직사각형은 한번에 그려진다는 것을 발견했다

따라서 BFS 탐색을 사용하여 한 붓 그리기 형식으로 문제를 접근했다

또한 한점은 상하좌우 로 선의 여부를 저장하기 위해 비트마스킹 을 사용했다

 

전체적인 문제의 흐름은 아래와 같다

1. 입력받은 좌표를 우리가 사용할 수 있는 형태로 변환한 후, 직사각형을 그린다
2. 각 시작지점을 반복문으로 돌며 BFS 탐색을 수행한다
3. 만약 이미 방문한 지점이라면 탐색을 수행하지 않는다
4. 만약 방문 도중 시작지점을 만났다면 이는 제외한다

 

 

[테스트케이스]

http://hsin.hr/2009/index.html

 

 

 

소스코드

문제 해결 시간 : 1h 50m

메모리 : 7016 KB

시간 : 4 ms

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
#define N 500
#define INF 987654321
using namespace std;

typedef pair<int, int> node;

int n,ans;
int x1,y1,x2,y2;
bool is_startPoint;
int map[MAX][MAX];
bool visited[MAX][MAX];

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

vector<node> s;

void makeRectangle(int xx1,int yy1,int xx2,int yy2){
    // 세로선 체크
    for(int i=xx1; i<xx2; i++){
        // 왼쪽 선
        map[i][yy1] |= (1<<2);
        map[i+1][yy1] |= (1<<0);
        
        // 오른쪽 선
        map[i][yy2] |= (1<<2);
        map[i+1][yy2] |= (1<<0);
    }
    
    // 가로선 체크
    for(int j=yy1; j<yy2; j++){
        // 위쪽 선
        map[xx1][j] |= (1<<1);
        map[xx1][j+1] |= (1<<3);
        
        // 아래쪽 선
        map[xx2][j] |= (1<<1);
        map[xx2][j+1] |= (1<<3);
    }
}

void bfs(int r,int c){
    queue<node> q;
    q.push(node(r,c));
    visited[r][c] = true;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        // 스타트 포인트
        if(x == N && y == N)
            is_startPoint = true;
        
        for(int i=0; i<4; i++){
            if(map[x][y] & (1<<i)){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(!visited[nx][ny]){
                    q.push(node(nx,ny));
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> y1 >> x1 >> y2 >> x2;
        makeRectangle(N+x1,N+y1,N+x2,N+y2);
        
        s.push_back(node(N+x1,N+y1));
    }
    
    memset(visited, false, sizeof(visited));
    ans = 0;
    
    // 한 붓 그리기
    for(int i=0; i<s.size(); i++){
        int x = s[i].first;
        int y = s[i].second;
        
        if(!visited[x][y]){
            is_startPoint = false;
            bfs(x,y);
            
            // 한 붓 그리기 도중 로봇의 시작점을 만나지 않았다면
            if(!is_startPoint)
                ans++;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}