[BOJ] 3108 - 로고 JAVA

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

예제 입력 1

5

1 1 4 4

3 3 6 6

4 4 5 5

5 0 8 3

6 1 7 2

예제 출력 1

2

 

 

 

 

 

 

 

풀이 1. (틀린 코드, 접근법 자체가 틀렸다)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Pair implements Comparable<Pair>{
    int r;
    int c;
    @Override
    public int compareTo(Pair o) {
        return this.r < o.r ? -1 : 1;  // 대각선 방향에 있으므로 row만 검사해도 충분하다
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static Pair[][] input = null;
    static boolean[][] check = null;

    static int n, maxRow, maxCol;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void dfs(int r, int c) {
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(-1 < nr && nr <= maxRow && -1 < nc && nc <= maxCol) {
                if(!check[nr][nc] && map[nr][nc] == 1) {
                    check[nr][nc] = true;
                    dfs(nr, nc);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        input = new Pair[n][2];  // input[] = 직사각형의 꼭지점 Pair 두개를 저장

        // x, y 입력은 그냥 row, col 입력으로 본다. row, col 순서가 바뀌게 되지만 무방하다.
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            input[i][0] = new Pair();
            input[i][1] = new Pair();
            for(int j = 0; j < 4; j++) {
                // map을 배열로 표현하기 위해 좌표평면 범위를 -500~500에서 0~1000으로 변경
                // 입력을 받으면서 max row, max col을 찾는다.
                int temp = Integer.parseInt(st.nextToken());
                if(j == 0) input[i][0].r = temp;
                else if(j == 1) input[i][0].c = temp;
                else if(j == 2) input[i][1].r = temp;
                else if(j == 3) input[i][1].c = temp;

                // map 크기를 정하기 위한 find max row, max col
                if(j % 2 == 0) maxRow = Math.max(maxRow, temp);
                else maxCol = Math.max(maxCol, temp);
            }
            Arrays.sort(input[i]);  // 더 큰 좌표의 꼭지점부터 입력된다는 보장 없음. 정렬 필요.
        }

        // 입력받은 꼭지점을 사용해 직사각형의 모든 좌표를 찾아 표시
        map = new int[maxRow + 1][maxCol + 1];
        check = new boolean[maxRow + 1][maxCol + 1];
        for(int i = 0; i < n; i++) {
            int r1 = input[i][0].r, c1 = input[i][0].c;
            int r2 = input[i][1].r, c2 = input[i][1].c;
            while(r1 <= r2) map[r1++][c1] = 1; r1--;
            while(c1 <= c2) map[r1][c1++] = 1; c1--;

            r1 = input[i][0].r;
            c1 = input[i][0].c;
            while(c1 <= c2) map[r1][c1++] = 1; c1--;
            while(r1 <= r2) map[r1++][c1] = 1; r1--;
        }

        int ans = 0;
        for(int i = 0; i <= maxRow; i++) {
            for(int j = 0; j <= maxCol; j++) {
                if(!check[i][j] && map[i][j] == 1) {
                    check[i][j] = true;
                    dfs(i, j);
                    ans += 1;
                }
            }
        }
        if(map[500][500] == 1) ans -= 1;  // 시작 위치가 사각형의 변에 들어가는 경우엔 1을 빼준다.
        System.out.println(ans);
    }
}

 

구현은 헷갈리는 부분이 많지만 개념 자체는 쉬운 문제라고 생각했다.

 

완벽한 착각.

 

사각형의 변이 지나는 모든 좌표에 점을 찍은 후 DFS를 돌려서 Component의 개수를 세는 문제라고 생각했다.

하지만 예제 입출력부터 틀려버린다.

 

내 생각대로라면 예제에서 주어진 사각형의 좌표에 점을 찍으면 아래 사진같은 형태가 나오는데, 

이런 형태이기 때문에 PU를 한 번만 수행하면 그 이후론 모든 사각형을 한 번에 그려낼 수 있을 거라 생각했다.

 

하지만 사각형의 변은 '선'이다. 저렇게 1씩 떨어져있는 점들로만 이뤄지지 않는다는 것이다.

그냥 단순하게 DFS 탐색 형태를 생각하다보니 스스로 함정에 빠져버렸다.

 

점이 아닌 선을 찍어봐야 제대로 된 모양을 알 수 있다.

선을 이으면 아래와 같다.

우측 하단의 동심사각형에서 PU를 한 번 더 실행해야 한다는 걸 알 수 있다.

 

결국 접근법 자체를 처음부터 다시 생각해야 한다.

 

 

 

 

 

풀이 2. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Pair implements Comparable<Pair>{
    int r;
    int c;
    @Override
    public int compareTo(Pair o) {
        return this.r < o.r ? -1 : 1;  // 대각선 방향에 있으므로 row만 검사해도 충분하다
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static Pair[][] input = null;
    static int n, ans, maxRow, maxCol;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        input = new Pair[n][2];  // input[] = 직사각형의 꼭지점 Pair 두개를 저장

        // x, y 입력은 그냥 row, col 입력으로 본다. row, col 순서가 바뀌게 되지만 무방하다.
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            input[i][0] = new Pair();
            input[i][1] = new Pair();
            for(int j = 0; j < 4; j++) {
                // map을 배열로 표현하기 위해 좌표평면 범위를 -500~500에서 0~1000으로 변경
                // 입력을 받으면서 max row, max col을 찾는다.
                int temp = Integer.parseInt(st.nextToken()) + 500;
                if(j == 0) input[i][0].r = temp;
                else if(j == 1) input[i][0].c = temp;
                else if(j == 2) input[i][1].r = temp;
                else if(j == 3) input[i][1].c = temp;

                // map 크기를 정하기 위한 find max row, max col
                if(j % 2 == 0) maxRow = Math.max(maxRow, temp);
                else maxCol = Math.max(maxCol, temp);
            }
            Arrays.sort(input[i]);  // 더 큰 좌표의 꼭지점부터 입력된다는 보장 없음. 정렬 필요.
        }

        // 입력받은 꼭지점을 사용해 직사각형의 모든 좌표를 찾아 표시
        map = new int[maxRow + 1][maxCol + 1];
        for(int i = 0; i < n; i++) {
            int r1 = input[i][0].r, c1 = input[i][0].c;
            int r2 = input[i][1].r, c2 = input[i][1].c;

            boolean isOverlap = false;
            while(r1 <= r2) {
                if(map[r1][c1] == 0) map[r1][c1] = 1;
                else isOverlap = true;
                r1 += 1;
            }
            r1--;

            c1++;
            while(c1 <= c2) {
                if(map[r1][c1] == 0) map[r1][c1] = 1;
                else isOverlap = true;
                c1 += 1;
            }
            c1--;

            r1 = input[i][0].r;
            c1 = input[i][0].c + 1;
            while(c1 <= c2) {
                if(map[r1][c1] == 0) map[r1][c1] = 1;
                else isOverlap = true;
                c1 += 1;
            }
            c1--;

            r1++;
            while(r1 != r2) {
                if(map[r1][c1] == 0) map[r1][c1]= 1;
                else isOverlap = true;
                r1 += 1;
            }
            r1--;

            if(!isOverlap) ans += 1;
        }

        if(map[500][500] == 1) ans -= 1;  // 시작 위치가 사각형의 변에 들어가는 경우엔 1을 빼준다.
        System.out.println(ans);
    }
}

 

사각형 경로에 있는 점을 하나씩 찍어나갈 때, 이미 찍혀있는 점에 또 찍어야 하는 경우는 이전에 그린 사각형과 겹친다는 뜻.

 

즉, 겹칠 때는 ans += 1을 하지 않고 겹치지 않을 때만 ans += 1을 하는 식으로 고쳤다.

 

솔직히 아직도 왜 틀린지 모르겠다.

 

아무 도움도 받지 않고 처음부터 내가 짠 코드를 포기하지 못 해서 이런식으로 시간을 날리게 되는 경우가 너무 많다.

안 되겠다 싶을 때는 과감하게 전부 엎어버리고 남의 코드를 보는 게 맞는 걸 알면서도 그러기가 쉽지 않다.

 

 

 

 

 

 

풀이 3. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Rectangle {
    int x1, y1, x2, y2;
    Rectangle(int x1, int y1, int x2, int y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static Rectangle[] map = null;
    static boolean[] check = null;
    static int n, ans;

    public static boolean isOverlap(Rectangle a, Rectangle b) {  // 사각형 겹침 여부 판단
        int aLeft, aRight, aTop, aBottom;
        int bLeft, bRight, bTop, bBottom;

        // 아래 조건 중 하나라도 TRUE라면 두 사각형은 절대 겹치지 않는다.
        // 1. A의 오른쪽이 B의 왼쪽보다 더 왼쪽에 있는 경우
        // 2. A의 왼쪽이 B의 오른쪽보다 더 오른쪽에 있는 경우
        // 3. A의 위쪽이 B의 아래쪽보다 더 아래쪽에 있는 경우
        // 4. A의 아래쪽이 B의 위쪽보다 더 위쪽에 있는 경우
        // 여기에 추가로 한 사각형이 다른 사각형 안에 내포된 경우까지 고려해야 함

        // 입력받은 두 점이 정렬 되어있다는 보장이 없으므로 왼, 오, 위, 아래 전부 직접 찾아줘야 한다.
        
        // find a left, right
        if(a.x1 < a.x2) { aLeft = a.x1; aRight = a.x2; }
        else { aLeft = a.x2;aRight = a.x1; }

        // find a top, bottom
        if(a.y1 < a.y2) { aBottom = a.y1; aTop = a.y2; }
        else { aBottom = a.y2; aTop = a.y1; }

        // find b left, right
        if(b.x1 < b.x2) { bLeft = b.x1; bRight = b.x2; }
        else { bLeft = b.x2; bRight = b.x1; }

        // find b top, bottom
        if(b.y1 < b.y2) { bBottom = b.y1; bTop = b.y2; }
        else { bBottom = b.y2; bTop = b.y1; }

        if(aLeft > bRight || aRight < bLeft || aTop < bBottom || aBottom > bTop ||
                (aLeft < bLeft && aRight > bRight && aTop > bTop && aBottom < bBottom) ||  // a가 b를 내포
                (bLeft < aLeft && bRight > aRight && bTop > aTop && bBottom < aBottom)) {  // b가 a를 내포
            return false;
        }else {
            return true;
        }
    }

    public static void dfs(int idx) {  // 점 단위가 아니라 하나의 사각형을 최소단위로 하여 탐색한다.
        for(int i = 0; i < n; i++) {
            if(!check[i] && isOverlap(map[i], map[idx])) {  // 사각형이 겹치면 이동 가능
                check[i] = true;
                dfs(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new Rectangle[n];
        check = new boolean[n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            map[i] = new Rectangle(x1, y1, x2, y2);

            // 시작점에 사각형이 있는 경우
            if((x1 == 0 && (y1 <= 0 && y2 >= 0)) || (x2 == 0 && (y1 <= 0 && y2 >= 0)))
                ans = -1;
        }

        for(int i = 0; i < n; i++) {
            if(!check[i]){
                check[i] = true;
                dfs(i);
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

 

훨씬 깔끔한 코드.

 

굳이 하나의 점을 최소단위로 잡아야만 DFS, BFS가 가능한 게 아니란 것을 배웠다.

하나의 사각형을 단위로 잡아 DFS를 전개했다.

 

사각형이 겹치면 인접한 노드로 판단하여 탐색을 전개할 수 있다.

 

이 때, 겹침 여부를 판단할 때 한 번 더 함정에 빠졌다.

 

일반적으로 사용되는 사각형 겹침 조건으로 겹침 여부를 판단하면 한 사각형이 다른 사각형을 완전히 내포하고있는 경우에서 오류가 발생한다.

 

사각형의 면적은 겹치는 게 맞지만 문제에서는 사각형의 변이 겹치는지를 확인해야하기 때문에 조건을 추가하여 검사해야 한다.