[Python] 백준 1186 직사각형 색칠하기

문제 링크 : https://www.acmicpc.net/problem/1186

1186번: 직사각형 색칠하기

1. 접근 방법

어떻게든 그리디 한 방법이나, 스위핑 같은 방법을 고민했는데, 여러 직 사각형이 겹치는 경우의 해결 방법이 떠오르지 않아, 전체 탐색을 고민했다.

최대 50개 직사각형을 탐색해서 50 * 50으로 각 직사각형마다 겹치는지 확인할 수 있고, 각 직사각형이 최대로 많이 탐색해도 50 * 8 정도라 생각하여 최대 1,000,000번의 탐색으로 가능할 것이라 생각하여 시도했고, 실제로도 잘 작동했다.

 

 

2. 풀이 코드

🖥python 코드

import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


def compare_box(box: list) -> list:
    x1, y1, x2, y2 = MIIS()
    # 더 낮은 번호 가진 직사각형들 가려지는지 확인
    for i in range(len(box)):
        prev_box = []
        for x3, y3, x4, y4 in box[i]:
            # 완전 겹쳐질 때
            if x1 <= x3 and y1 <= y3 and x2 >= x4 and y2 >= y4:
                continue
            # 겹치지 않을 때
            elif x1 >= x4 or x2 <= x3 or y1 >= y4 or y2 <= y3:
                prev_box.append((x3, y3, x4, y4))
            # 일부만 겹쳐질 때
            else:
                # 완전 내부
                if x1 > x3 and y1 > y3 and x2 < x4  and y2 < y4:
                    prev_box += [
                        (x3, y2, x1, y4), (x1, y2, x2, y4), (x2, y2, x4, y4), (x3, y1, x1, y2),
                        (x2, y1, x4, y2), (x3, y3, x1, y1), (x1, y3, x2, y1), (x2, y3, x4, y1)
                    ]
                # 2등분
                elif x1 <= x3 and y1 <= y3 and x3 < x2 < x4 and y2 >= y4:
                    prev_box.append((x2, y3, x4, y4))
                elif x3 < x1 < x4 and y1 <= y3 and x2 >= x4 and y2 >= y4:
                    prev_box.append((x3, y3, x1, y4))
                elif x1 <= x3 and y1 <= y3 and x2 >= x4 and y3 < y2 < y4:
                    prev_box.append((x3, y2, x4, y4))
                elif x1 <= x3 and y3 < y1 < y4 and x2 >= x4 and y2 >= y4:
                    prev_box.append((x3, y3, x4, y1))
                # 3등분 
                elif x3 < x1 < x4 and y1 <= y3 and x3 < x2 < x4 and y2 >= y4:
                    prev_box += [(x3, y3, x1, y4), (x2, y3, x4, y4)]
                elif x1 <= x3 and y3 < y1 < y4 and x2 >= x4 and y3 < y2 < y4:
                    prev_box += [(x3, y3, x4, y1), (x3, y2, x4, y4)]
                # 6등분
                elif x3 < x1 < x4 and y3 < y1 < y4 and x3 < x2 < x4 and y2 >= y4:
                    prev_box += [
                        (x3, y1, x1, y4), (x2, y1, x4, y4), (x3, y3, x1, y1), 
                        (x1, y3, x2, y1), (x2, y3, x4, y1)
                    ]
                elif x3 < x1 < x4 and y3 < y1 < y4 and x2 >= x4 and y3 < y2 < y4:
                    prev_box += [
                        (x3, y2, x1, y4), (x1, y2, x4, y4), (x3, y1, x1, y2), 
                        (x3, y3, x1, y1), (x1, y3, x4, y1)
                    ]
                elif x3 < x1 < x4 and y1 <= y3 and x3 < x2 < x4 and y3 < y2 < y4:
                    prev_box += [
                        (x3, y2, x1, y4), (x1, y2, x2, y4), (x2, y2, x4, y4), 
                        (x3, y3, x1, y2), (x2, y3, x4, y2)
                    ]
                elif x1 <= x3 and y3 < y1 < y4 and x3 < x2 < x4 and y3 < y2 < y4:
                    prev_box += [
                        (x3, y2, x2, y4), (x2, y2, x4, y4), (x2, y1, x4, y2), 
                        (x3, y3, x2, y1), (x2, y3, x4, y1)
                    ]
                # 4등분
                elif x1 <= x3 and y2 >= y4 and x3 < x2 < x4 and y3 < y1 < y4:
                    prev_box += [(x3, y3, x2, y1), (x2, y3, x4, y1), (x2, y1, x4, y4)]
                elif x2 >= x4 and y2 >= y4 and x3 < x1 < x4 and y3 < y1 < y4:
                    prev_box += [(x3, y3, x1, y1), (x1, y3, x4, y1), (x3, y1, x1, y4)]
                elif x1 <= x3 and y1 <= y3 and x3 < x2 < x4 and y3 < y2 < y4:
                    prev_box += [(x2, y3, x4, y2), (x3, y2, x2, y4), (x2, y2, x4, y4)]
                elif x2 >= x4 and y1 <= y3 and x3 < x1 < x4 and y3 < y2 < y4:
                    prev_box += [(x3, y3, x1, y2), (x3, y2, x1, y4), (x1, y2, x4, y4)]
        box[i] = prev_box
    # 지금 직사각형 추가
    box.append([(x1, y1, x2, y2)])
    return box


def calc_box_size(box_now: list) -> int:
    size = 0
    for x1, y1, x2, y2 in box_now:
        size += (x2 - x1) * (y2 - y1)
    return size


K, N = MIIS()
box = []
for _ in range(K):
    box = compare_box(box)

# 각 직사각형이 보이는 영역 넓이 구하기
box_size_viewd = []
for idx, box_now in enumerate(box):
    box_size_viewd.append((calc_box_size(box_now), idx))
# 정렬
box_size_viewd.sort(key=lambda x:(-x[0], x[1]))

ans = []
for _, idx in box_size_viewd[:N]:
    ans.append(idx + 1)
print(*sorted(ans))

📕코드 해설

전체 탐색이다보니 코드는 길지만 중복되는 부분이 많다.

탐색 순서는 다음과 같다.

    1. 각 직사각형을 입력받아

    2. 해당 직사각형보다 더 번호가 작은 모든 직사각형을 확인하고

    3. 모든 직사각형이 겹치는 부분을 제외하고 다시 저장한다.

우선 각 두 개의 직사각형이 가능한 배치 형태는 다음과 같다.

문제 풀이에서 왼쪽 위부터 오른쪽으로, 아래로 순서대로 겹치지 않을 때, 정말 내부, 완전 겹칠 때, 2등분, 3등분, 4등분, 6등분으로 주석이 달려 있는 부분에 해당한다.

각각 겹쳐진 후에도 보이는 부분을 리스트에 저장했는데, 처음에는 단순하게 나뉘는 모든 부분을 저장했다.

위와 같은 경우 총 9개 구분된 영역 중 8개를 저장했는데, 최소한으로 저장한다면 다름과 같이 할 수 있다.

만약 문제를 해결하려 한다면, 최소한으로 저장하여 푸는 방법도 좋을 것 같다.

이후에는 각 저장된 영역의 크기 내림차순으로, 인덱스를 오름차순으로 정렬해서 출력하면 된다.

 

 

3. 생각 정리

단순히 앞의 중요한 문제에 매료되어, 작지만 중요한 문제를 망각하는 것 같다.

이 문제도, 시도해보진 않았지만, 거의 절반 정도의 구분된 영역으로 해결할 수 있다.