[백준] 로고

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

3108번: 로고

개인적으로 재미있었던 문제입니다. 유니온-파인드를 활용하여 푸는 문제입니다. 이 문제의 포인트는 3가지입니다. 첫번째는 연필을 올리기는 작업이 필요한 경우는 서로 포함관계가 없는 직사각형이 존재할 때 연필 올리기 작업이 필요하다는 것입니다.  따라서, 겹치는 사각형들은 하나의 그룹으로 만들어주면 됩니다. 두번째는 포함관계를 어떻게 찾을 것인가에 대한 것입니다. 저는 한 직사각형의 가로변과 다른 사각형의 세로변이 교차하는지를 체크해주었습니다(isCross 함수). 마지막으로는 (0, 0)을 지나는 변이 있는 사각형을 포함하는 그룹은 최초에 (0, 0)에서 시작하므로 연필 올리기 작업이 필요하지 않습니다. 이에 대한 체크가 있어야 정해를 구할 수 있습니다.

 

import sys, heapq
from collections import defaultdict

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

def getSquare(y1, x1, y2, x2):
    if y1 < y2 and x1 < x2:
        return (y1, x1, y2 - y1, x2 - x1)
    elif y1 < y2 and x1 > x2:
        return (y1,x2, y2 - y1, x1 - x2)
    elif y1 > y2 and x1 > x2:
        return (y2, x2, y1 - y2, x1 - x2)
    elif y1 > y2 and x1 < x2:
        return (y2, x1, y1 - y2, x2 - x1)


def isCross(hy1, hy2, hx, wy, wx1, wx2):
    if min(wx1, wx2) <= hx <=  max(wx1, wx2) and min(hy1, hy2) <= wy <=  max(hy1, hy2):
        return True

    return False


def isOverlapped(p1, p2):
    y1, x1, h1, w1 = p1
    y2, x2, h2, w2 = p2

    for x in range(x1, x1 + w1 + 1, w1):
        for y in range(y2, y2 + h2 + 1, h2):
            if isCross(y1, y1 + h1, x, y, x2, x2 + w2):
                return True
    for x in range(x2, x2 + w2 + 1, w2):
        for y in range(y1, y1 + h1 + 1, h1):
            if isCross(y2, y2 + h2, x, y, x1, x1 + w1):
                return True

    return False

squares = []

parent = [x for x in range(n)]

for _ in range(n):
    x1, y1, x2, y2 = tuple(map(int, input().split()))

    left_y, left_x, h, w = getSquare(y1, x1, y2, x2)
    squares.append((left_y, left_x, h, w))


def find(p):
    if p == parent[p]:
        return p

    parent[p] = find(parent[p])

    return parent[p]

for i in range(n):
    for j in range(i + 1, n):
        p1 = squares[i]
        p2 = squares[j]

        if not isOverlapped(p1, p2):
            continue

        pa = find(i)
        pb = find(j)

        if pa == pb:
            continue

        if pa < pb:
            parent[pb] = pa
        else:
            parent[pa] = pb

visited = [False] * n
ans = 0

for i in range(n):
    pi = find(i)

    if not visited[pi]:
        visited[pi] = True
        ans += 1


flag = False

for y, x, h, w in squares:
    if y <= 0 <= y + h and (x == 0 or x + w == 0):
       flag = True
       break

    if x <= 0 <= x + w and (y == 0 or y + h == 0):
        flag = True
        break

if flag:
    print(ans - 1)
else:
    print(ans)