[Python] 3108번 로고

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

3108번: 로고

---

 

22/09/22

 

 

유니온-파인드(분리 집합)와 두 직사각형이 만나는 함수를 섞으면 쉽게 풀 수 있는 문제이다.

 

유니온-파인드의 기본 난이도가 골드 5인데, 이 문제에서 유니온-파인드를 사용해야 된다는 점을 캐치하는 것, 그리고 두 직사각형이 만나는 함수를 구현하는 난이도, 그리고 약간의 예외처리를 고려하자면 저 난이도는 굉장히 적절한 난이도라고 생각한다.

---

 

문제 접근 방식:

 

 

PU명령은 펜을 떼라는 명령이다.

 

이 문제는 PU명령을 최소화 하면서 주어진 직사각형을 다 그리게끔 하고 싶은 것이다.

 

그리고 그 때의 PU명령의 최솟값을 구하는 것이다.

 

우리는 만약 두 직사각형이 서로 교차한다면, 두 직사각형을 모두 펜을 떼지 않고 그릴 수 있다는 사실을 알고 있다.

 

다시 말해, 만약 두 직사각형이 만나지 않는다면 무조건 펜을 한 번은 떼야만 그릴 수 있다는 뜻이다.

여러 직사각형끼리 만나서 붙어있는 거를 하나의 "그룹"이라고 하면, 우리는 한 "그룹"을 펜을 떼지 않고 그릴 수 있다.(PU명령이 필요 없음.)

따라서, PU명령의 최솟값을 구하라는 뜻은, 분리 집합을 이용하여 직사각형 "그룹"의 개수가 몇 개인지 구하라는 뜻과 거의 같다.

이때, 문제에서 주어지기를 같은 선을 여러 번 그릴 수 있지만, 직사각형 N개를 제외한 어떤 것도 그릴 수 없다고 했고, 제일 처음의 거북이의 위치는 (0,0)에 위치해 있다고 했으므로, "그룹"의 개수를 다 구한 뒤에 만약 그룹들 중에서 점 (0, 0)을 포함하고 있는 그룹이 있다면 그 그룹은 처음에 펜을 안 떼고 그릴 수 있으므로 그룹의 개수에서 1을 빼준 것이 PU명령의 최솟값이다.

만약 그렇지 않다면, 그냥 그룹의 개수가 PU명령의 최솟값이다.

 

구현 방법은 모든 직사각형을 돌면서 두 직사각형이 만나면 유니온을 시켜준다.(이때의 시간복잡도는 O(n^2))

 

이후 파인드 함수를 전부 돌면서 대표노드를 통일시켜준다.

 

이후 모든 직사각형을 돌면서 원점을 포함하는 직사각형이 있으면 전체 개수에서 1을 빼주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3108번 로고
# 자료 구조, 기하학, 분리 집합, 많은 조건 분기
'''
접근 방법:

PU명령은 펜을 떼라는 명령이다.

만약 두 직사각형이 서로 교차하는 점이 있다면,
우리는 그 두 직사각형을 펜을 떼지 않고 그릴 수 있음.
만약 두 직사각형이 만나지 않는다면, 무조건 펜을 한번은 떼야만 그릴 수 있다.

직사각형끼리 만나서 붙어있는 거를 "그룹"이라고 정의하자.
우리는 "그룹"을 펜을 떼지 않고 그릴 수 있다.(PU명령이 필요 없음)

따라서 PU명령의 최솟값을 구하라는 뜻은,
분리 집합을 이용하여 직사각형 "그룹"의 개수가 몇개인지 구하라는 뜻과 거의 같다.

이때, 문제에서 주어지기를 같은 선을 여러 번 그릴 수 있지만,
직사각형 N개를 제외한 어떤 것도 그릴 수 없다고 했고,
제일 처음의 거북이의 위치는 (0,0)에 위치해 있다고 했으므로,

그룹의 개수를 다 구한 뒤에 만약 직사각형들 중에서 점 (0, 0)을 포함하고 있는 직사각형이 있다면
그 그룹은 처음에 펜을 안떼고 그릴 수 있으므로 그룹의 개수에서 1을 빼준 것이 PU명령의 최솟값이다.

만약 그렇지 않다면, 그냥 그룹의 개수가 PU명령의 최솟값이다.

직사각형의 개수가 1000개로 주어지고, 시간 제한이 1초 이므로 O(n^2)의 시간 복잡도로 구현 가능하다.
'''
import sys
input = sys.stdin.readline

def is_two_rectangle_meet(rect1, rect2):
    if (rect1[1][0] < rect2[0][0] or rect2[1][0] < rect1[0][0] or
        rect1[0][1] > rect2[1][1] or rect2[0][1] > rect1[1][1]):  # 아예 만나지 않을 때
        return False
    elif ((rect1[0][0] < rect2[0][0] < rect2[1][0] < rect1[1][0] and
          rect1[0][1] < rect2[0][1] < rect2[1][1] < rect1[1][1]) or
          (rect2[0][0] < rect1[0][0] < rect1[1][0] < rect2[1][0] and
          rect2[0][1] < rect1[0][1] < rect1[1][1] < rect2[1][1])): # 면적이 겹치지만 안에 쏙 들어가있을 때
        return False
    else:
        return True
def is_contain_origin(rect):
    if (0 not in rect[0]) and (0 not in rect[1]):
        return False
    elif rect[0][0]*rect[1][0] > 0 or rect[0][1]*rect[1][1] > 0:
        return False
    else:
        return True
def find(node):
    if reps[node] != node:
        reps[node] = find(reps[node])
    return reps[node]
def union(node1, node2):
    rep1 = find(node1)
    rep2 = find(node2)
    reps[rep2] = rep1

N = int(input())
reps = list(range(N))
rects = []
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    rects.append(((x1, y1), (x2, y2)))

for i in range(N-1):
    for j in range(i+1, N):
        if is_two_rectangle_meet(rects[i], rects[j]):
            union(i, j)

for i in range(N):
    find(i)

total = len(set(reps))
for i in range(N):
    if is_contain_origin(rects[i]):
        total -= 1
        break

print(total)