백준(BOJ) 3108 : 로고 (JAVA)

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

3108번: 로고

거북이는 같은 선을 여러 번 그릴 수 있다. 따라서 교차하는 직사각형들을 한 그룹으로 보고(교차할 경우, 한 번에 다 그릴 수 있으므로) 그룹의 개수를 구하면 되는 문제이다.

 

위 그림을 예로 들면, 교차하는 직사각형의 그룹이 총 3개이므로, 로고는 총 3번의 PU 명령어를 통해 모든 직사각형을 그릴 수 있다.

 

교차하는 직사각형의 그룹의 개수를 구하는 방법은, 각 직사각형들이 교차하는 지의 여부를 인접행렬에 저장해놨다가 DFS를 통해 개수를 구한다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Rectangle[] rectangles = new Rectangle[n];
        boolean[][] intersect = new boolean[n][n];
        boolean crossZero = false;
        
        for(int i = 0; i < n; i++) {
            StringTokenizer 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());
            
            rectangles[i] = new Rectangle(x1, y1, x2, y2);
            
            if(y1 == 0 && x1 * x2 <= 0 || y2 == 0 && x1 * x2 <= 0 || x1 == 0 && y1 * y2 <= 0 || x2 == 0 && y1 * y2 <= 0) {
                crossZero = true;
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(rectangles[i].intersect(rectangles[j])) {
                    intersect[i][j] = true;
                }
            }
        }
        
        boolean[] visited = new boolean[n];
        int cnt = 0;
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs(rectangles, intersect, visited, i,  n);
                cnt++;
            }    
        }
        
        if(crossZero) cnt--;
        
        System.out.println(cnt);
    }
 
    private static void dfs(Rectangle[] rectangles, boolean[][] intersect, boolean[] visited, int i, int n) {
        visited[i] = true;
        
        for(int j = 0; j < n; j++) {
            if(!visited[j] && intersect[i][j]) {
                dfs(rectangles, intersect, visited, j, n);
            }
        }
    }
 
    private static class Rectangle {
        private int x1;
        private int y1;
        private int x2;
        private int y2;
        
        public Rectangle(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
 
        public int getX1() {
            return x1;
        }
 
        public int getY1() {
            return y1;
        }
 
        public int getX2() {
            return x2;
        }
 
        public int getY2() {
            return y2;
        }
        
        public boolean intersect(Rectangle rectangle) {
            int _x1 = rectangle.getX1();
            int _y1 = rectangle.getY1();
            int _x2 = rectangle.getX2();
            int _y2 = rectangle.getY2();
            
            return !(_x2 < x1 || x2 < _x1 || _y2 < y1 || y2 < _y1 || (x1 < _x1 && x2 > _x2 && y1 < _y1 && y2 > _y2) || (_x1 < x1 && _x2 > x2 && _y1 < y1 && _y2 > y2));
        }
    }
}

여기서 조심해야할 것이 있는데, 직사각형 중 원점(0, 0)을 지나는 게 있는지의 여부이다. 하나라도 원점을 지나는 직사각형이 있을 경우, 거북이가 처음 PU명령어를 사용할 필요가 없어지므로, 이 때의 답은 '직사각형 그룹의 갯수 - 1'이 된다. 

 

그리고 두 직사각형이 교차하는 지의 여부를 구하는 조건이 좀 복잡하다;;

혹시 더 쉬운 방법을 아는 분은 댓글을 남겨주시면 감사하겠습니다.(굽신굽신)