108. 로고 (백준 3108) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/3108

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명령의 최솟값을 출력한다.

풀이

FA, LT, RT, PD 이런거에 현혹되면 안되고, 결국 구해야 하는건 PU. 즉 몇번 떼고 그려야하냐이다

겹쳐진 직사각형은 안떼고 그릴 수 있으므로, 결국 어떤 직사각형들이 겹쳐있는지만 확인하면 된다.

우선 x1, y1이 가장 왼쪽의 지점이고, x2,y2가 가장 오른쪽 지점이 되도록 입력을 조정한다.

이후 두 직사각형이 겹치는지 확인하는방법은 아래 6가지가 아니면 겹치는거다.

N이 1000개이므로, N*N에 일일히 각 직사각형들이 겹치는지 관계를 체크하면 된다.

이때 편의를 위해 (0,0,0,0)-시작점 의 직사각형도 같이 넣어서 계산해준다.

이후에는 원점부터 시작해서 -> 겹친 사각형 다 탐색 -> 이후에 겹친애들의 겹친애들 다 탐색....

BFS를 통해 진행하다, 더이상 진행 불가능 (겹치는게 없을때) 일때 +1해주고 방문 안한애로 다시 시작하면된다.

코드

package com.algo;

import java.io.*;
import java.util.*;

public class Main {

    //start point = 0,0
    //PU (점 내리기)의 횟수 구하기
    //만약 직사각형이 겹치지 않음 -> 손올리기 -> 손내리기 해야함
    //직사각형이 겹치는 경우 -> 한붓그리기 가능

    static int N;
    static int[][] squares;
    static boolean[] drawed;
    static boolean[][] crossed;
    static int answer = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        squares = new int[N+1][4];
        int x1,x2,y1,y2;


        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            if(x1 > x2){
                squares[i][0] = x2;
                squares[i][2] = x1;
            }else {
                squares[i][0] = x1;
                squares[i][2] = x2;
            }
            if(y1 > y2){
                squares[i][1] = y2;
                squares[i][3] = y1;
            }else {
                squares[i][1] = y1;
                squares[i][3] = y2;
            }
        }
        drawed = new boolean[N+1];
        crossed = new boolean[N+1][N+1];

        for(int i=0; i<N+1; i++){
            for(int j=i+1; j<N+1; j++){
                if(isDest(i,j)){
                    crossed[i][j] = true;
                    crossed[j][i] = true;
                }

            }
        }
        Wu(0);
        System.out.println(answer);

    }

    public static void Wu(int init){
        Queue<Integer> q = new LinkedList<>();
        q.add(init);
        drawed[init] = true;
        int cur;

        while(!q.isEmpty()){
            cur = q.poll();
            for(int i=1; i<N+1; i++){
                if(crossed[cur][i] && !drawed[i]){
                    q.add(i);
                    drawed[i] = true;
                }
            }
        }

        for(int i=0; i<N+1; i++){
            //안칠한애 나옴
            if(!drawed[i]){
                answer++;
                Wu(i);
                return;
            }
        }
    }

    public static boolean isDest(int cur, int next){
        if(squares[next][2] < squares[cur][0]) return false;
        if(squares[next][3] < squares[cur][1]) return false;
        if(squares[next][0] > squares[cur][2]) return false;
        if(squares[next][1] > squares[cur][3]) return false;
        if(squares[next][0] > squares[cur][0] && squares[next][2] < squares[cur][2]
                && squares[next][1] > squares[cur][1] && squares[next][3] < squares[cur][3]) return false;
        if(squares[next][0] < squares[cur][0] && squares[next][2] > squares[cur][2]
                && squares[next][1] < squares[cur][1] && squares[next][3] > squares[cur][3]) return false;


        return true;
    }
}

결과