1569. [Python]정사각형으로 가리기

1. 문제

 

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

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 많은 조건 분기

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

N = int(input())

square_point = set()

min_x = sys.maxsize
max_x = -sys.maxsize
min_y = sys.maxsize
max_y = -sys.maxsize

check_list = []

for _ in range(N):
    point = tuple(map(int,input().split()))
    check_list.append(point)
    min_x = min(min_x, point[0])
    min_y = min(min_y, point[1])
    max_x = max(max_x, point[0])
    max_y = max(max_y, point[1])
    # 최대 x, y / 최소 x, y 좌표 구하기
    y_total = max_y - min_y
    x_total = max_x - min_x
    #  x, y 좌표의 차이 값 구하기

# 정답 체크할 변수
flag = False

# y좌표 길이가 더 긴 경우
if y_total > x_total:
    # 두 좌표의 길이차 구해두기
    max_distance = y_total - x_total
    #  정사각형을 만드는 좌표 개수 체크
    cnt = 0
    for k in check_list:
        # y 좌표가 더 길기때문에 최대 x 좌표에서 길이 차만큼 더한 범위에 x값이 있고 y 좌표가 최대 or 최소 y인 경우 / 최대 최소 x 좌표값과 같고 최대 최소 y 좌표값 사이의 경우 cnt 값 증가
        if ((min_x <= k[0] <= max_x + max_distance) and ( min_y == k[1] or max_y == k[1])) or ((min_x == k[0] or max_x + max_distance == k[0]) and (min_y <= k[1] <= max_y)):
            cnt += 1
    # cnt 값이 N 과 같은 경우 정답을 출력할 변수 True
    if cnt == N:
        flag = True

    cnt = 0
    for k in check_list:
        # y 좌표가 더 길기때문에 최소 x 좌표에서 길이 차만큼 뺀 범위에 x값이 있고 y 좌표가 최대 or 최소 y인 경우 / 최대 최소 x 좌표값과 같고 최대 최소 y 좌표값 사이의 경우 cnt 값 증가
        if ((min_x - max_distance <= k[0] <= max_x) and (min_y == k[1] or max_y == k[1])) or ((min_x - max_distance == k[0] or max_x == k[0]) and (min_y <= k[1] <= max_y)):
            cnt += 1
    
    # cnt 값이 N 과 같은 경우 정답을 출력할 변수 True
    if cnt == N:
        flag = True
# x 좌표가 더 긴 경우
elif y_total < x_total:

    max_distance = x_total - y_total
    cnt = 0
    for k in check_list:
            # x 좌표가 더 길기때문에 최대 y 좌표에서 길이 차만큼 더한 범위에 y값이 있고 x 좌표가 최대 or 최소 x인 경우 / 최대 최소 y 좌표값과 같고 최대 최소 x 좌표값 사이의 경우 cnt 값 증가
        if (( min_x == k[0] or max_x == k[0] ) and (min_y <= k[1] <= max_y + max_distance)) or ((min_x <= k[0] <= max_x) and (min_y == k[1] or k[1] == max_y + max_distance)):
            cnt += 1

    if cnt == N:
        flag = True

    cnt = 0
    for k in check_list:
        # x 좌표가 더 길기때문에 최소 y 좌표에서 길이 차만큼 뺀 범위에 y값이 있고 x 좌표가 최대 or 최소 x인 경우 / 최대 최소 y 좌표값과 같고 최대 최소 x 좌표값 사이의 경우 cnt 값 증가
        if (( min_x == k[0] or max_x == k[0] ) and (min_y - max_distance <= k[1] <= max_y)) or ((min_x <= k[0] <= max_x ) and (min_y - max_distance == k[1] or max_y == k[1])):
            cnt += 1
    
    if cnt == N:
        flag = True

else:
    cnt = 0
    for k in check_list:
        # 길이가 같은 경우는 x 좌표 고정 y 범위 / y 좌표 고정 x 범위 만 확인해보면 된다.
        if (( min_x == k[0] or max_x == k[0]) and (min_y <= k[1] <= max_y)) or ((min_x <= k[0] <= max_x) and (min_y == k[1] or max_y == k[1])):
            cnt += 1
    if cnt == N:
        flag = True

if flag:
    print(max(y_total,x_total))
else:
    print(-1)

 

4. 문제를 풀고난 후 생각

 

• 문제를 접하며 많은 고민을 했던 문제였다. 처음에는 정사각형이 되는지 조건을 체크하는 것부터 시작을 했었다.
• 정사각형이 아니라도 y좌표, x좌표중 더 긴것중에 정사각형을 만들때 점이 들어가 있는지 체크를 해야 하는 부분도 고려했어야 하는 문제이다.
• 처음에 생각했던 방법은 그저 긴 길이를 구한 후 그 길이만큼 짧은 길이를 +, - 방향으로 연장시켜서 모두 확인해보는 것을 생각 했지만, 이 생각이 잘못됐다는 것을 늦게 깨달았다.
• 짧은 길이의 좌표를 + 한 경우 그 + 한 범위 내에서 있는지 체크를 해야했고, - 한 경우 - 한 범위 내에서만 있는지 체크를 진행했어야 했다. 간단하게 그림으로 보여주면 아래와 같다.

 

 

• 위 그림처럼 1번에서는 1번 범위에 점이 들어있는지 체크하고 2번 범위에 점이 들어있는지 체크를 진행하게 된다.
• 한 케이스에서 더 긴쪽을 기준으로 이 경우를 동시에 체크를 진행하고 둘중에 일치하는 값이 있는 경우 긴쪽을 기준으로 정사각형을 구성하였으므로 정답을 출력해주면 된다.
• 조건 분기가 많아서 처음 조건을 설정하는 부분이 어려웠던 문제였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 많은 조건 분기