[BOJ 20041, Python 3] Escaping
https://www.acmicpc.net/problem/20041
20041번: Escaping
첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌
www.acmicpc.net
풀이
문제에서 예시 그림을 제공하여 쉽게 이해할 수 있던 문제입니다.
잘 생각해보면 도둑은 상하좌우 네 방향중 한 곳으로 쭉 도망치는 것이 제일 효율적으로 도망치는 것을 알 수 있습니다.
왜냐하면 만약 도둑이 원래 가던 방향이 아닌 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)으로 좌표변환을 할 때 계산을 이상하게 해서 몇 번 틀렸네요..
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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')
|
cs |