[BOJ][Python]1569 풀이

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

1569번: 정사각형으로 가리기

import sys
ssr = sys.stdin.readline

def is_available_a(points, x, y, l):
    for i in points:
        if x <= i[0] <= x+l and (i[1] == y or i[1] == y+l):
            continue
        elif (i[0] == x or i[0] == x+l) and y <= i[1] <= y+l:
            continue
        else:
            return False
    else:
        return True
    
def is_available_b(points, x, y, l):
    for i in points:
        if x-l <= i[0] <= x and (i[1] == y or i[1] == y+l):
            continue
        elif (i[0] == x-l or i[0] == x) and y <= i[1] <= y+l:
            continue
        else:
            return False
    else:
        return True
    
def is_available_c(points, x, y, l):
    for i in points:
        if x <= i[0] <= x+l and (i[1] == y-l or i[1] == y):
            continue
        elif (i[0] == x or i[0] == x+l) and y-l <= i[1] <= y:
            continue
        else:
            return False
    else:
        return True
    
def is_available_d(points, x, y, l):
    for i in points:
        if x-l <= i[0] <= x and (i[1] == y-l or i[1] == y):
            continue
        elif (i[0] == x-l or i[0] == x) and y-l <= i[1] <= y:
            continue
        else:
            return False
    else:
        return True
    
n = int(ssr())
points = [list(map(int, ssr().split())) for _ in range(n)]
minx, miny = min([points[i][0] for i in range(n)]), min([points[i][1] for i in range(n)])
maxx, maxy = max([points[i][0] for i in range(n)]), max([points[i][1] for i in range(n)])
l = max(maxx - minx, maxy - miny)
    
if is_available_a(points, minx, miny, l) or is_available_b(points, maxx, miny, l) or is_available_c(points, minx, maxy, l) or is_available_d(points, maxx, maxy, l):
    print(l)
else:
    print(-1)

처음에는 브루트포스로 풀었습니다. 간단하게 풀고 넘어가려고 했는데 생각보다 오래걸렸고 런타임도 별로입니다. N의 최대가 50이고 나올 수 있는 좌표의 절댓값도 1000이 최대니까 2000 * 2000 * 50의 경우에 대해서만 판단하면 되니까 2억번의 경우니까 시간 초과는 안나겠더라구요.

 

그 다음에는 4가지 경우에 대해서 테스트를 진행했습니다. 제가 생각했던 반례인데,

4

0 1

0 2

0 3

-1 3

의 경우에 시작 위치를 minx, miny로 진행할 때 문제가 생기더라구요. 그러면 좌표가 어떻게 될지는 모르겠지만 이런 비슷한 다른 경우(maxx, maxy로 시작하거나, 섞어서 진행할 때에도)들 중에 하나만 성공하면 가능하다는 판단을 해줘야 할 필요가 있었습니다.

 

다만 좀 더 코드 자체의 길이를 짧게 짜보고 싶은데 약간 생각이 잘 안나네요.

추가// 코드 길이를 좀 줄여봤습니다.

import sys
ssr = sys.stdin.readline

def is_available(points, x, y, l):
    for i in points:
        if min(x, x+l) <= i[0] <= max(x, x+l) and (i[1] == y or i[1] == y+l):
            continue
        elif (i[0] == x or i[0] == x+l) and min(y, y+l) <= i[1] <= max(y, y+l):
            continue
        else:
            return False
    else:
        return True
    
n = int(ssr())
points = [list(map(int, ssr().split())) for _ in range(n)]
minx, miny = min([points[i][0] for i in range(n)]), min([points[i][1] for i in range(n)])
maxx, maxy = max([points[i][0] for i in range(n)]), max([points[i][1] for i in range(n)])
l = max(maxx - minx, maxy - miny)
    
if is_available(points, minx, miny, l) or is_available(points, maxx, miny, l) or is_available(points, minx, maxy, l) or is_available(points, maxx, maxy, -l):
    print(l)
else:
    print(-1)