백준 3108. 로고 :: 돼지개발자

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

"연결 요소의 개수. 빠진 조건이 없나 다시보자. 그리고 아이디어"

 해당 문제를 하루 동안 붙잡고 있었다. 어떤 문제든 주어지는 조건을 잘 봐야겠다. 

이 문제는 연결 요소의 개수를 구하는 문제로 처음에는 각 좌표에다가 +500 씩해서 모든 직사각형을 map에 체크하려고 했다. 

하다보니 하나의 사각형이 내포되면서 접하고 있는 사각형 두개의 경우 탐색이 불가능한 것을 알았고, *2를 해서 벌려 놓을까 하다가 

비효율적인 것 같아서 아래 방법으로 풀었다.

BFS를 통해서 연결된 직사각형을 구한다. 이 과정에서 각각의 직사각형들이 서로 연결되어 있는지 확인해야 하는데, 나는 연결 되어 있

지 않은 경우를 체크했다. 비교는 x1,y1,x2,y2 로 비교 가능하다. (대각선을 이루는 각 점의 대소 관계를 또 빠트려서 고생..)

1.사각형 A의 왼쪽/오른쪽/아래/위 에 사각형 B가 있는 경우

2.사각형 A가 사각형 B를 내포하고 있는 경우

3.사각형 A가 사각형 B에 의해 내포된 경우 

나는 3번의 경우를 생각하지 못해서 계속 일부 테스트 케이스가 틀렸었다. BFS를 이용해 연결 요소의 개수를 구할 준비가 되었다.

그런데 여기서 한가지 더 체크해야 될 부분이 있다. 거북이는 0,0 에서 시작하고 있다는 것. 따라서 어떤 직사각형이 0,0 을 지나간다면 원래 

구해야 할 답에서 -1 을 빼줘야 한다. 

어떻게 처리 할까? 나는 초기 입력 받을 때, 0 을 지나가는 직사각형이 있는지 확인해서 있다면, cnt = -1 로 셋팅 해주었다.

근데 다른 소스를 참고해보니... 아하... 아이디어가 있었다. 애초에 0,0,0,0 점 하나를 map에 포함시켜 두어 무조건 -1 을 빼주면 되는 것.

아이디어다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N;
    static Rec[] map;
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();
    static int cnt;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new Rec[N+1];
        visited = new boolean[N+1];
        
        map[0] = new Rec(0, 0, 0, 0);
        
        for (int i = 1; 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());
            map[i] = new Rec(x1, y1, x2, y2);
        }
        
        for (int i = 0; i <= N; i++) {
            if(visited[i]) continue;
            
            visited[i] = true;
            q.add(i);
            
            while(!q.isEmpty()) {
                int cur = q.poll();
                
                for (int j = 0; j <= N; j++) {
                    
                    if(cur == j || !check(cur, j) || visited[j]) 
                        continue;
                    
                    visited[j] = true;
                    q.add(j);
                }
            }
            cnt++;
        }
        System.out.println(cnt-1);
    }
    
    static boolean check(int cur, int next) {
        Rec c = map[cur];
        Rec n = map[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 || c.x1 > n.x2 || c.y2 < n.y1 || c.y1 > n.y2 )
            return false;
        
        return true;
    }
}
 
class Rec {
    int x1;
    int y1;
    int x2;
    int y2;
    
    Rec(int x1, int y1, int x2, int y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}