[백준] 3108 로고 java

import java.io.*;
import java.util.*;
class Rect {
    int x1;
    int y1;
    int x2;
    int y2;
    Rect(int x1, int y1, int x2, int y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}

public class Logo {
    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static int ans;
    static boolean[] checked;
    static Rect[] rectArr;
    static Queue<Integer> q;
    public static void main(String[] args) throws IOException{
        input();
        bfs();
        System.out.println(ans-1);
    }

    public static void input() throws IOException{
        br = new BufferedReader(new InputStreamReader(System.in));
        ans = 0;
        n = Integer.parseInt(br.readLine());
        rectArr = new Rect[n+1];
        checked = new boolean[n+1];
        rectArr[0] = new Rect(0, 0, 0, 0);
        for(int i = 1; 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());
            rectArr[i] = new Rect(x1, y1, x2, y2);
        }
    }

    public static void bfs() {
        q = new LinkedList<>();

        for(int i = 0; i <= n; i++) {
            if(checked[i]) continue;
            checked[i] = true;
            q.add(i);
            while(!q.isEmpty()) {
                int cur = q.poll();
                for(int j = 0; j <= n; j++) {
                    //현재와 같거나 접점이 없거나 이미 방문한 경우는 제외
                    if(cur == j || !checkConnected(cur, j) || checked[j]) continue;
                    checked[j] = true;
                    q.add(j);
                }
            }
            ans++;
        }
    }

    public static boolean checkConnected(int cur, int next) {
        Rect c = rectArr[cur];
        Rect n = rectArr[next];
        if((c.x1 < n.x1 && n.x2 < c.x2 && c.y1 < n.y1 && n.y2 < c.y2)
                || (c.x1 > n.x1 && n.x2 > c.x2 && c.y1 > n.y1 && n.y2 > c.y2)
                || (c.x2 < n.x1 || n.x2 < c.x1 || c.y2 < n.y1 || n.y2 < c.y1)) {
            return false;
        }
        return true;
    }
}

문제를 풀 때 마다 나는 말하는 감자란걸 느낀다.. bfs를 좀 더 다양하게 쓸 수 있구나란 생각이 드는 동시에 이렇게 풀 생각을 한번에 하는 사람들은 정말 머리가 비상하구나 라고 느꼈다. 나는 그저 계속 (풀이를 보며) 풀어갈뿐..

 

이 문제의 핵심 아이디어는 n개의 직사각형 중에서 다른 직사각형과 접점이 없는 직사각형의 갯수를 세면 된다. 명령어는 크게 신경을 안써도 될 것이 어처피 거북이가 펜을 드는 최소값을 찾는 것이니 다른 명령어는 신경 쓸 필요가 없다.

그리고 접점이 있는 직사각형들은 이어서 그릴 수가 있기때문에 묶어서 하나로 생각할 수 있다.

 

그렇다면 접점이 없는 직사각형은 어떻게 판별할 수 있을까?

 

1. A가 B를 완전히 내포하고 있는 경우

2. A가 B에 내포되고 있는 경우

3. 상, 하, 좌, 우 완전히 접점이 없는 경우

 

이렇게 판별 메서드를 만들어서 BFS를 구현해 접점이 있다고 판단되면 계속해서 다른 직사각형들이 접점이 있는지 탐색한다. 그리고 탐색이 끝나면 Count를 하나 추가해준다. 

 

하지만 이렇게 되면 작은 문제가 하나 발생한다. 0, 0에서 거북이가 펜을 내리고 시작하니 만약 n개의 직사각형 중에 0,0 좌표에 접점이 있는 직사각형이 있을 경우 나온 답에서 -1을 해주어야 한다. 

 

그러려면 입력받은 직사각형 중에 0, 0을 지나는 직사각형이 있는지 확인해서 있다면 -1을 해주어야 하는데 그럼 비효율적이니 애초에 0, 0, 0, 0을 하나 넣어둬서 (펜이 내려져서 시작하니) 처음부터 바로 나아가고 무조건 -1을 해주면 된다.