[BaekJoon] 3108 로고 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int N;
    static List<Rectangle> rectangles;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        rectangles = new ArrayList<>();
        rectangles.add(new Rectangle(new int[] {0, 0}, new int[] {0, 0}));

        for(int idx = 0; idx < N; idx++) {
            int leftX = scanner.nextInt(), leftY = scanner.nextInt(), rightX = scanner.nextInt(), rightY = scanner.nextInt();
            rectangles.add(new Rectangle(new int[] {leftX, leftY}, new int[] {rightX, rightY}));
        }
    }

    static void solution() {
        int answer = 0;
        boolean[] visited = new boolean[N + 1];

        for(int idx = 0; idx <= N; idx++) {
            if(!visited[idx]) {
                visited[idx] = true;
                bfs(idx, visited);
                answer++;
            }
        }

        System.out.println(answer - 1);
    }

    static void bfs(int index, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(index);

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            for(int idx = 0; idx <= N; idx++) {
                if(idx == index || visited[idx] || !rectangles.get(cur).isOverlapped(rectangles.get(idx))) continue;
                visited[idx] = true;
                queue.offer(idx);
            }
        }
    }

    static class Rectangle {
        int[] leftBottom, rightTop;

        public Rectangle(int[] leftBottom, int[] rightTop) {
            this.leftBottom = leftBottom;
            this.rightTop = rightTop;
        }

        boolean isOverlapped(Rectangle rectangle) {
            if(leftBottom[0] < rectangle.leftBottom[0] && leftBottom[1] < rectangle.leftBottom[1]
            && rectangle.rightTop[0] < rightTop[0] && rectangle.rightTop[1] < rightTop[1]) return false;

            if(leftBottom[0] > rectangle.leftBottom[0] && leftBottom[1] > rectangle.leftBottom[1]
                    && rectangle.rightTop[0] > rightTop[0] && rectangle.rightTop[1] > rightTop[1]) return false;

            if(rightTop[1] < rectangle.leftBottom[1] || rightTop[0] < rectangle.leftBottom[0]
            || leftBottom[0] > rectangle.rightTop[0] || leftBottom[1] > rectangle.rightTop[1]) return false;

            return true;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 서로 겹쳐있는 직사각형들은 펜을 떼지 않고 그릴 수 있습니다. 그렇기 때문에 겹쳐있는 직사각형 집합의 개수를 구하면 이 문제의 답을 구할 수 있습니다.
• 그런데 시작 지점이 (0, 0)이기 때문에 해당 위치 또한 겹쳐지는 직사각형에 포함시켜야 합니다. 즉, (0, 0)에서 펜을 떼서 어떠한 위치로 이동해야 하는 것인지, 혹은 (0, 0)부터 바로 직사각형을 그릴 수 있는지 판단하기 위해 (0, 0) 위치 또한 겹쳐지는 직사각형에 포함시켜야 합니다.
• 각 직사각형이 겹쳐지는 조건을 아래와 같습니다.

boolean isOverlapped(Rectangle rectangle) {
    if(leftBottom[0] < rectangle.leftBottom[0] && leftBottom[1] < rectangle.leftBottom[1]
    	&& rectangle.rightTop[0] < rightTop[0] && rectangle.rightTop[1] < rightTop[1]) return false;

    if(leftBottom[0] > rectangle.leftBottom[0] && leftBottom[1] > rectangle.leftBottom[1]
        && rectangle.rightTop[0] > rightTop[0] && rectangle.rightTop[1] > rightTop[1]) return false;

    if(rightTop[1] < rectangle.leftBottom[1] || rightTop[0] < rectangle.leftBottom[0]
    	|| leftBottom[0] > rectangle.rightTop[0] || leftBottom[1] > rectangle.rightTop[1]) return false;

    return true;
}

• BFS를 통하여 한 직사각형과 겹쳐지는 직사각형을 찾고 그러한 직사각형을 제외한 나머지 직사각형에서 또 겹쳐지는 직사각형들을 찾으며 겹쳐지는 직사각형 집합의 개수를 구합니다.