[Python/파이썬] 백준 3108번 로고

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

코드

import sys
input = sys.stdin.readline


class Square:
    def __init__(self, x1, y1, x2, y2):
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2

    def meet(self, square):
        if self.x1 < square.x1 and self.y1 < square.y1 and self.x2 > square.x2 and self.y2 > square.y2:
            return False
        if self.x1 > square.x1 and self.y1 > square.y1 and self.x2 < square.x2 and self.y2 < square.y2:
            return False
        if self.x1 > square.x2 or self.y2 < square.y1 or self.x2 < square.x1 or self.y1 > square.y2:
            return False
        return True


n = int(input())
squares = []
parent = [i for i in range(n+1)]
squares.append(Square(0, 0, 0, 0))


def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]


def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a == b:
        return
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


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

for i in range(n+1):
    for j in range(i+1, n+1):
        if (squares[i].meet(squares[j])):
            union(i, j)

for i in range(n+1):
    parent[i] = find_parent(i)

print(len(set(parent))-1)

 

이거 처음에는 구현 문제인가?싶었는데 자세히 보니 분리집합 문제였다.

PU 명령의 최솟값을 구하는 것이므로 한 번 연필을 내렸을 때 그릴 수 있는 직사각형의 집합이 몇 개 있느냐를 구하면 된다. 여기서 직사각형의 같은 집합에 속하는 경우는 연필을 떼지 않고 한 번에 그릴 수 있도록 겹치는 부분이 있는 경우이다. 예를 들자면, 아래와 같은 경우 3개의 직사각형이 모두 같은 집합에 속한다고 본다.

이런 집합이 몇 개 존재하는지 구하면 연필을 최소한으로 떼면서 다 그리는 횟수를 구할 수 있다.

 

이걸 구하기 위해서는 분리집합을 사용하면 된다. 사실 아주 기본적인 분리집합 알고리즘을 적용하면 풀 수 있는거라서 그건 쉬운데 직사각형이 겹치는지 구하는게 조금 헷갈렸다. 여기서는 직사각형을 표현할 때 square라는 클래스를 만들어서 사용했는데, `meet` 함수가 자기자신과 인자로 들어온 다른 직사각형이 겹치는지 구하는 메서드이다. 

일단 겹치지 않을 수 있는 경우를 구하고 그 경우에만 `False`를 리턴하도록 메서드를 구현했다.

def meet(self, square):
    if self.x1 < square.x1 and self.y1 < square.y1 and self.x2 > square.x2 and self.y2 > square.y2:
        return False
    if self.x1 > square.x1 and self.y1 > square.y1 and self.x2 < square.x2 and self.y2 < square.y2:
        return False
    if self.x1 > square.x2 or self.y2 < square.y1 or self.x2 < square.x1 or self.y1 > square.y2:
        return False
    return True

 

이 메서드로 두 직사각형이 겹치는지, 안 겹치는지 구해서 만약 겹친다면 `union()`으로 같은 집합에 넣어주면 된다. 최종적으로는 집합의 개수-1이 답이 된다. 1을 빼는 이유는 처음에 연필이 (0, 0)에 내려가 있는데, 이것도 고려하기 위해 처음에 squares에 `(0, 0, 0, 0)`을 넣어놨기 때문이다.