[BOJ 20041, Python 3] Escaping

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

20041번: Escaping

 

풀이

문제에서 예시 그림을 제공하여 쉽게 이해할 수 있던 문제입니다.

잘 생각해보면 도둑은 상하좌우 네 방향중 한 곳으로 쭉 도망치는 것이 제일 효율적으로 도망치는 것을 알 수 있습니다.

왜냐하면 만약 도둑이 원래 가던 방향이 아닌 90도 직각으로 꺾어서 한 칸 이동하면 경찰도 그만큼 한 칸 더 이동하여 방어적으로 펼칠 수 있기 때문입니다.

 

경찰의 위치는 (x, y)라고 하고, 도둑은 (Sx, Sy)라고 하면 경찰이 도둑을 막을 수 있는 방법은 (Sx, y)나 (x, Sy)로 이동하는 선택지만 남게됩니다.

여기서도 abs(Sx - x) == abs(Sy - y)가 아니라면 한 방향으로만 막을 수 있는 것이죠(두 방향을 막는 경우는 본문 탈출 불가능 예시 사진 참조)

 

이해를 쉽게하기 위해 도둑의 위치를 (0, 0)으로 잡아봅시다.

만약 경찰의 위치는 (1, 9)라고 하면 경찰은 (0, 9)로 이동하여 한 칸만 이동하여 도둑이 윗방향으로 9칸을 가야 도착할 좌표에 미리 대기하여 막을 수 있습니다. 하지만 경찰이 (1, 0)으로 이동한다면 경찰은 아홉칸을 이동해야 (1, 0)에 도착하지만, 도둑은 한 칸만 이동하면 (1, 0)에 도착해서 도둑이 이미 도망갈 수 있으니 저 경찰은 한 방향으로만 막을 수 있는 것이 최선입니다.

 

만약 경찰의 위치가 (-5, -3)이라고 하면 경찰은 (-5, 0)으로 이동하여 3칸만 이동하여 도둑이 왼쪽으로 5칸 가야 도착할 좌표를 미리 대기하여 막을 수 있습니다. (0, -3)으로 이동한다면 위와 같은 이유로 도둑을 막을 수 없습니다.

 

이렇게 상하좌우 네 방향의 bool변수를 만들어서 위와 같은 방법으로 도둑이 도망칠 수 있는 곳이 존재하면 YES, 아니라면 NO를 출력하면 됩니다.

도둑의 위치를 (0, 0)으로 좌표 변환을 한다면 제 1사분면, 제 2사분면, ... 이렇게 확인할 수 있어서 더 좋은 것 같습니다.

 

 

저는 if문을 도배해서 풀었는데, 더 간단한 코드가 분명 있을겁니다.

도둑의 위치를 (0, 0)으로 좌표변환을 할 때 계산을 이상하게 해서 몇 번 틀렸네요..

코드

input = __import__('sys').stdin.readline
n = int(input())
arr = [[*map(int, input().split())] for _ in range(n)]
sx, sy = map(int, input().split())
up, down, left, right = True, True, True, True
for i in range(n):
    arr[i][0] -= sx
    arr[i][1] -= sy
for x, y in arr:
    if x >= 0 and y >= 0:
        if x == y: up, right = False, False
        elif min(x, y) == x: up = False
        else: right = False
    if x >= 0 and y <= 0:
        if x == abs(y): right, down = False, False
        elif min(x, abs(y)) == x: down = False
        else: right = False
    if x <= 0 and y >= 0:
        if abs(x) == y: left, up = False, False
        elif min(abs(x), y) == abs(x): up = False
        else: left = False
    if x <= 0 and y <= 0:
        if abs(x) == abs(y): left, down = False, False
        elif min(abs(x), abs(y)) == abs(x): down = False
        else: left = False
if up or down or left or right: print('YES')
else: print('NO')