[ BOJ / Python ] 15937번 두 박스

이번 문제는 수많은 조건들을 정의해 해결해야 하는 문제였다.

처음에는 단순하게 인접 행렬 형식의 그래프를 만든 후, 두 박스의 영역을 1로 갱신한 후, DFS를 통해 그래프를 순회하며 전체 넓이를 구하고, 두 박스의 좌표로 넓이를 구한 후, 두 넓이를 비교하여 1차이 날 경우 POINT, 1보다 많이 차이 날 경우 맞닿는 선분이 있으면 LINE, 없으면 FACE, 두 넓이가 같다면 NULL을 출력하도록 하였다.

ax, ay, bx, by=map(int, input().split())
cx, cy, dx, dy=map(int, input().split())
mx_num=max(ax, ay, bx, by, cx, cy, dx, dy)
graph=[[0]*(mx_num+1) for _ in range(mx_num+1)]
for x in range(ax, bx+1):
    graph[x][ay:by+1]=[1]*(by-ay+1)
for x in range(cx, dx+1):
    graph[x][cy:dy+1]=[1]*(dy-cy+1)
dx=[0, 0, -1, 1]
dy=[1, -1, 0, 0]
visited=[[False]*(mx_num+1) for _ in range(mx_num+1)]
def get_width(x, y, result):
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<=mx_num and 0<=ny<=mx_num and graph[nx][ny]==1 and not visited[nx][ny]:
            visited[nx][ny]=True
            result=get_width(nx, ny, result+1)
    return result
cur=0
for i in range(mx_num+1):
    for j in range(mx_num+1):
        if graph[i][j]==1 and not visited[i][j]:
            cur+=get_width(i, j, 0)
origin=(ax-bx+1)*(ay-by+1)+(cx-dx+1)*(dy1-cy+1)
if origin-cur==1:
    print('POINT')
elif origin-cur>1:
    if bx==cx or by==cy:
        print('LINE')
    else:
        print('FACE')
elif origin-cur==0:
    print('NULL')

그러나 이 풀이는 조건도 조금 부족하고, 무엇보다도 메모리 초과가 발생한다. 메모리 초과 없이 문제를 해결하기 위해서는 계산이 아닌 오직 조건을 비교하여 답을 도출해야 한다는 사실을 알게 되었다. 조건이 매우 까다로웠기 때문에 다른 사람의 풀이를 참고하였다.

ax, ay, bx, by=map(int, input().split())
cx, cy, dx, dy=map(int, input().split())
def point():
    if (ax,ay)==(dx,dy) or (bx,by)==(cx,cy) or (bx,ay)==(cx,dy) or (ax,by)==(dx,cy):
        return True
    else:
        return False
def line():
    if (((bx, by) == (cx, dy) and by > cy) or (((bx, ay) == (cx, cy) and dy > ay)) or ((dx, cy) == (ax, ay) and by > cy) or ((dx, dy) == (ax, by) and dy > ay) or ((bx, by) == (cx, dy) and (bx, ay) == (cx, cy)) or ((ax, ay) == (dx, cy) and (dx, dy) == (ax, by)) or ((cx, cy) == (ax, by) and (bx, by) == (dx, cy)) or ((ax, ay) == (cx, dy) and (dx, dy) == (bx, ay)) or (ax == dx and (ay < cy < by or ay < dy < by)) or (bx == cx and (ay < cy < by or ay < dy < by)) or (by == cy and (ax < cx < bx or ax < dx < bx)) or (ay == dy and (ax < cx < bx or ax < dx < bx)) or (ax == dx and (cy < ay < dy or cy < by < dy)) or (bx == cx and (cy < ay < dy or cy < by < dy)) or (by == cy and (cx < ax < dx or cx < bx < dx)) or (ay == dy and (cx < ax < dx or cx < bx < dx))):
        return True
    else:
        return False
def null():
    if bx<cx or dx<ax or by<cy or dy<ay:
        return True
    elif bx-ax<dx-cx and by-ay<dy-cy and (cx<ax<dx and cx<bx<dx) and (cy<ay<dy and cy<by<dy):
        return True
    elif bx-ax>dx-cx and by-ay>dy-cy and (ax<cx<bx and ax<dx<bx) and (ay<cy<by and ay<dy<by):
        return True
    else:
        return False
if line():
    print('LINE')
elif point():
    print('POINT')
elif null():
    print('NULL')
else:
    print('FACE')