[유니온-파인드] 백준 3108번: 로고 / 골드 3

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

3108번: 로고

import sys
input = sys.stdin.readline

n = int(input())
points = []

original = False
for i in range(n):
    a, b, c, d = map(int, input().split())
    points.append([a, b, c, d])

    if a == 0 or c == 0:
        if b <= 0 <= d:
            original = True

    if b == 0 or d == 0:
        if a <= 0 <= c:
            original = True

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

def isCrossed(i , j):
    x1, y1, x2, y2 = points[i]
    x3, y3, x4, y4 = points[j]

    if x3 > x2 or x4 < x1 or y3 > y2 or y4 < y1:
        return False

    if x1 < x3 and x4 < x2 and y1 < y3 and y4 < y2:
        return False

    if x3 < x1 and x2 < x4 and y3 < y1 and y2 < y4:
        return False

    return True

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

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

for i in range(n-1):
    for j in range(i+1, n):
        if isCrossed(i, j):
            union(i, j)

count = 0
for i in range(n):
    if parent[i] == i:
        count += 1

if original:
    print(count -1)
    #print(len(set(parent))-1)
else:
    print(count)
    #print(len(set(parent)))

오개념 하나랑 모르고 있던 개념 하나 때문에 굉장히 오래 걸린 문제다. 

 

 

1. 직사각형의 교차여부

도저히 모르겠어서 이 부분은 구글링 참고를 하였다.

def isCrossed(i , j):
    x1, y1, x2, y2 = points[i]
    x3, y3, x4, y4 = points[j]

    if x3 > x2 or x4 < x1 or y3 > y2 or y4 < y1:
        return False

    if x1 < x3 and x4 < x2 and y1 < y3 and y4 < y2:
        return False

    if x3 < x1 and x2 < x4 and y3 < y1 and y2 < y4:
        return False

    return True

- 첫번째 조건문 : 직사각형의 겹침 여부를 판단. 이때 직사각형은 내부 면적이 칠해져있다고 생각한다. 

따라서 첫번째 조건문만으로는 직사각형을 이루는 선끼리의 교차여부를 완벽히 알아낼 수 없다.

한 직사각형이 다른 직사각형을 내부에 포함시키고 있는 경우를 제외시켜 주어야 한다.

- 두번째 조건문: i-직사각형 내부에 j-직사각형이 들어가는 경우

- 세번째 조건문: j-직사각형 내부에 i-직사각형이 들어가는 경우

 

 

2. 나의 오개념

유니온-파인드를 시행하고 나서 네트워크의 개수를 알아낼 때 len(set(parent))를 해주었는데, 유니온-파인드를 시행한 후에 모든 parent 값이 루트 노드를 가리키고 있는 것은 아니었다. 따라서 이렇게 하면 올바른 네트워크 개수를 알아낼 수 없다.  

if original:
    print(count -1)
    #print(len(set(parent))-1)
else:
    print(count)
    #print(len(set(parent)))

 

- 네트워크 개수 알아내기

count = 0
for i in range(n):
    if parent[i] == i:
        count += 1