[코드트리] 잔해물을 덮기 위한 사각형의 최소 넓이

https://www.codetree.ai/missions/5/problems/minimum-area-of-rectangle-to-cover-debris?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

< 입력 형식 >

첫 번째 줄에 첫 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.

두 번째 줄에 두 번째 직사각형에 해당하는 좌측하단의 좌표와 우측상단의 좌표 (x1, y1), (x2, y2)가 공백을 사이에 두고 주어집니다.

• -1,000 ≤ x1 < x2 ≤ 1,000
• -1,000 ≤ y1 < y2 ≤ 1,000

< 풀이 >

모든 경우의 수를 생각해본다

빗금친 부분이 잔해의 넓이이고, 노란색 부분이 잔해를 덮는 가장 작은 직사각형의 넓이이다.

좌표가 마이너스값을 가질 수 있으므로 offset을 더해주는 함수 정의 -> map에서 사용할 예정

def setting(str):
    return int(str) + 1000

 

좌표평면을 다루기 위한 2차원 배열 선언

arr = [[0 for _ in range(2001)] for _ in range(2001)]

 

첫 번째 직사각형 -> 포함되는 범위 안에 있는 값 모두 1로 변경

x1_origin, y1_origin, x2_origin, y2_origin = map(setting, input().split())

for i in range(x1_origin, x2_origin):
    for j in range(y1_origin, y2_origin):
        arr[i][j] = 1

 

두 번째 직사각형 -> 포함되는 범위 안에 있는 값 모두 0으로 변경

이 때 두 사각형이 겹쳐지는 부위는 모두 0으로 바뀌게 된다.

x1, y1, x2, y2 = map(setting, input().split())

for i in range(x1, x2):
    for j in range(y1, y2):
        arr[i][j] = 0

 

잔해를 덮을 직사각형의 넓이가 최소가 되기 위해선 잔해를 덮을 정도만 되면 충분하다.

=> (한 행이 가지는 1의 개수의 최댓값) * (1이 하나 이상 있는 행의 개수)로 직사각형의 넓이를 산출할 수 있다.

따라서 이들을 다루는 변수를 선언한다.

max_v = 0
row_count = 0

 

탐색 범위를 첫 번째 직사각형이 갖는 좌표의 범위로 제한하고, 행을 탐색하면서 1의 개수의 최대값을 업데이트한다

1이 하나 이상 있으면 행 카운트를 하나 올린다.

for i in range(x1_origin, x2_origin):
    # 1의 개수(잔해물) 카운트
    count = 0
    for j in range(y1_origin, y2_origin):
        if arr[i][j] == 1:
            count += 1
    # 현재 행에 잔해물이 남아있다면 행 카운트를 하나 올림
    if count > 0:
        row_count += 1
    # 한 행이 가지는 1의 개수(잔해물) 최대값 업데이트
    if max_v < count:
        max_v = count

print(max_v * row_count)

 

하지만 여기에 문제가 있다.

5번과 같은 경우는 잔해가 두 부분이 생기는데,

이를 덮는 가장 작은 직사각형은 첫 번째 직사각형의 넓이와 같게 된다.

하지만 위에서 작성한 코드에 따르면 첫 번째 직사각형의 넓이보다 작게 출력될 것이다. (1이 있는 행만 카운트하므로)

아래 예시를 보자

따라서 이 케이스를 다루는 코드가 따로 필요하다.

# edge case (사각형이 2개로 쪼개지는 경우 [가로])
if (x1 < x1_origin and x2 > x2_origin and y1_origin < y1 < y2 < y2_origin) or\
x1_origin < x1 < x2 < x2_origin and y1 < y1_origin and y2 > y2_origin:
    print((x2_origin-x1_origin) * (y2_origin-y1_origin))

 

<코드 전체 보기>

def setting(str):
    return int(str) + 1000

arr = [[0 for _ in range(2001)] for _ in range(2001)]

x1_origin, y1_origin, x2_origin, y2_origin = map(setting, input().split())

for i in range(x1_origin, x2_origin):
    for j in range(y1_origin, y2_origin):
        arr[i][j] = 1

x1, y1, x2, y2 = map(setting, input().split())

for i in range(x1, x2):
    for j in range(y1, y2):
        arr[i][j] = 0

max_v = 0
row_count = 0

# edge case (사각형이 2개로 쪼개지는 경우 [가로])
if (x1 < x1_origin and x2 > x2_origin and y1_origin < y1 < y2 < y2_origin) or\
x1_origin < x1 < x2 < x2_origin and y1 < y1_origin and y2 > y2_origin:
    print((x2_origin-x1_origin) * (y2_origin-y1_origin))
else:
    for i in range(x1_origin, x2_origin):
        # 1의 개수(잔해물) 카운트
        count = 0
        for j in range(y1_origin, y2_origin):
            if arr[i][j] == 1:
                count += 1
        # 현재 행에 잔해물이 남아있다면 행 개수를 하나 올림
        if count > 0:
            row_count += 1
        # 한 행이 가지는 1의 개수(잔해물) 최대값 업데이트
        if max_v < count:
            max_v = count

    print(max_v * row_count)

< 느낀 점 >

코드트리에서는 문제를 틀릴 경우 몇번째 테스트 케이스에서 틀렸는지, 어떤 입력값이 들어왔는지 알려준다. 입력값을 보기 전에 최대한 내가 생각할 수 있는 선에서 반례를 생각해보았지만 잘 떠오르지 않아 결국 입력값을 열어보았는데, 미처 생각하지 못했던 엣지 케이스가 나왔다. 나름대로 사각형이 겹치게 되는 경우를 모두 고려했다고 생각했지만 이렇게 미처 생각하지 못한 부분이 있었기에, 오히려 이번 경험을 통해 테스트 코드의 중요성 및 엣지 케이스에 대한 예외처리가 중요하다는 것을 알게 되었다.