[Baekjoon] 로고(python)

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

문제 접근

이 문제를 풀기 위한 아이디어는 사각형끼리 교점이 있으면 같은 그룹으로 묶을 수 있고 같은 그룹이면 연필을 올리는 연산인 PU를 하지 않고도 한번에 그릴 수 있다는 것이었다.

또 시작 위치는 원점이고 방향은 위쪽을 보고 있으므로 사각형 그룹이 원점에서 바로 그릴 수 있으면 PU 명령을 할 필요가 없으나 그렇지 않은 경우는 반드시 PU 명령을 해야한다.

하지만 사각형을 그룹핑하기 위한 방법이 떠오르지 않아 풀이를 참조하여 Union-Find(합집합 찾기)를 이용하면 된다는 것을 알았다. 즉 Union-Find를 통해 사각형을 그룹핑하고 그룹의 갯수를 구하면 PU 명령을 실행해야할 횟수를 알 수 있다.

---

풀이 과정

이 문제의 풀이 코드이다. 각 사각형끼리 교차점이 있으면 같은 그룹으로 묶으면 된다.

for i in range(N - 1):
    for j in range(i + 1, N):
        if is_cross(i, j):
            union(i, j)

 

1. 사각형을 원점에서 그릴 수 있는지 확인

1) 원점에서 PU 명령없이 사각형을 그릴 수 있는 경우

2) 원점에서 PU 명령없이 사각형을 그릴 수 없는 경우

for _ in range(N):
    x1, y1, x2, y2 = list(map(int, sys.stdin.readline().split()))

    if x1 == 0 or x2 == 0:
        if y1 <= 0 <= y2:
            is_origin = True

    if y1 == 0 or y2 == 0:
        if x1 <= 0 <= x2:
            is_origin = True

 

2.사각형끼리 교차하는지 확인

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

    # 직사각형과 겹치지 않는 경우
    if x3 > x2 or x4 < x1 or y3 > y2 or y4 < y1:
        return False

    # i 사각형 안에 j 사각형이 들어있는 경우
    if x1 < x3 and x4 < x2 and y1 < y3 and y4 < y2:
        return False

    # j 사각형 안에 i 사각형이 들어가는 경우
    if x3 < x1 and x2 < x4 and y3 < y1 and y2 < y4:
        return False

    return True

 

3. 사각형 그룹핑

def union(u, v):
    u = find(u)
    v = find(v)

    if u < v:
        parent[v] = u
    else:
        parent[u] = v


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

 

4. 사각형 그룹 갯수

parent 배열에 초기값은 모두 자기 자신을 지정했다. 따라서 사각형 그룹핑을 완료했는데도 자기 자신이면 각 그룹의 최상위 부모라는 의미이기 때문에 parent가 자기 자신인 경우를 세어주면 된다.

count = 0

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

처음에는 list(set(parent))로 그룹의 갯수를 세었는데 Union-Find를 끝냈을 때 각 번호가 루트를 가리키는 게 아니기 때문에 올바른 방법이 아니었다.

---

정답 코드

"""
    백준 3108번 로고
"""
import sys

N = int(sys.stdin.readline())
rectangle = []
parent = [i for i in range(N)]

is_origin = False

for _ in range(N):
    x1, y1, x2, y2 = list(map(int, sys.stdin.readline().split()))

    if x1 == 0 or x2 == 0:
        if y1 <= 0 <= y2:
            is_origin = True

    if y1 == 0 or y2 == 0:
        if x1 <= 0 <= x2:
            is_origin = True

    rectangle.append([x1, y1, x2, y2])


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

    # 직사각형과 겹치지 않는 경우
    if x3 > x2 or x4 < x1 or y3 > y2 or y4 < y1:
        return False

    # i 사각형 안에 j 사각형이 들어있는 경우
    if x1 < x3 and x4 < x2 and y1 < y3 and y4 < y2:
        return False

    # j 사각형 안에 i 사각형이 들어가는 경우
    if x3 < x1 and x2 < x4 and y3 < y1 and y2 < y4:
        return False

    return True


def union(u, v):
    u = find(u)
    v = find(v)

    if u < v:
        parent[v] = u
    else:
        parent[u] = v


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


for i in range(N - 1):
    for j in range(i + 1, N):
        if is_cross(i, j):
            union(i, j)

count = 0

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

print(count if not is_origin else count - 1)