가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다.
이 격자판의 (0, 0) 칸에 한 마리의 뱀이 자리를 잡고 있다. 처음에는 뱀의 크기가 격자판의 한 칸의 크기와 같으며, 뱀의 머리는 격자판의 오른쪽을 바라보고 있다. 이 뱀은 자신이 바라보고 있는 방향으로 1초에 한 칸씩 몸을 늘려나가며, 뱀의 머리는 그 방향의 칸으로 옮겨가게 된다. 예를 들어 위의 그림과 같이 L = 3인 경우를 생각해 보자. 뱀은 처음에 (0, 0)에 있으며, 그 크기는 격자판 한 칸 만큼이고, 뱀의 머리가 바라보고 있는 방향은 오른쪽이다. 1초가 지나고 나면 이 뱀은 몸을 한 칸 늘려서 (0, 0)과 (1, 0)의 두 칸을 차지하게 되며, 이때 (1, 0) 칸에 뱀의 머리가 놓이게 된다. 1초가 더 지나고 나면 (0, 0), (1, 0), (2, 0)의 세 칸을 차지하게 되고, 뱀의 머리는 (2, 0)에 놓이게 된다.
이 뱀은 자신의 머리가 향하고 있는 방향을 일정한 규칙에 따라 시계방향, 혹은 반시계방향으로 90도 회전한다. 1번째 회전은 뱀이 출발한지 t1 초 후에 일어나며 i(i > 1)번째 회전은 i − 1번째 회전이 끝난 뒤 ti 초 후에 일어난다. 단, 뱀은 ti 칸 만큼 몸을 늘린 후에 머리를 회전하며 머리를 회전하는 데에는 시간이 소요되지 않는다고 가정한다.
만일 뱀의 머리가 격자판 밖으로 나가게 되면, 혹은 뱀의 머리가 자신의 몸에 부딪히게 되면 이 뱀은 그 즉시 숨을 거두며 뱀은 숨을 거두기 직전까지 몸을 계속 늘려나간다.
뱀이 머리를 회전하는 규칙, 즉 ti 와 그 방향에 대한 정보가 주어졌을 때, 뱀이 출발한지 몇 초 뒤에 숨을 거두는지를 알아내는 프로그램을 작성하라.
첫 번째 줄에 정수 L(1 ≤ L ≤ 10^8)이 주어진다. 두 번째 줄에는 머리의 방향을 몇 번 회전할 것인지를 나타내는 정수 N(0 ≤ N ≤ 10^3)이 주어진다. 다음 N 개의 줄에 뱀이 머리를 어떻게 회전하는지에 대한 정보가 주어진다. i(1 ≤ i ≤ N)번째 줄에 정수 t_i(1 ≤ t_i ≤ 2 · 10^8)와 dir_i 가 차례로 주어지며 dir_i 는 문자 L, 또는 R 중 하나이다. 뱀은 i = 1인 경우 출발, 그 외의 경우엔 i − 1번째 회전으로부터 t_i 초 후에 dir_i 의 방향으로 머리를 회전하며, 만일 dir_i 가 L 이라면 왼쪽 (반시계방향)으로, R 이라면 오른쪽 (시계방향)으로 90도 회전한다.
출력
첫 번째 줄에 답을 나타내는 값을 하나 출력한다. 이 값은 뱀이 출발한지 몇 초 후에 숨을 거두는지를 나타낸다.
입력 예시
3
4
2 L
2 L
1 L
5 R
출력 예시
7
풀이
교통사고 문제. 구현 문제인데도 불구하고 엄청 오래 해맸던 것 같다.
점, 그러니까 좌표를 기준으로 문제를 풀이하면 무조건 시간 초과 및 메모리 초과를 겪게 된다. 최대 크기가 2*10^8이므로.즉 점이 아닌 선을 기준으로 문제를 풀이해보면 된다.
지금까지 저장해 온 선들을 저장하였다고 가정하였을 때,
원래 좌표 (x, y)에서 다음 회전 시간 t_i까지의 이동 좌표 (ax, ay)를 구한다.
새로 생성된 선이 지금까지의 선들과 충돌하는지 여부를 검사한다.
만약 하나 이상이 충돌한다면, 충돌하는 최소 거리를 구한다. 두 선분 이상과 동시에 충돌할 수도 있다는 점을 명심하자.
수직으로 만나거나, 수평으로 만나는 경우로 나뉜다.
만약 충돌하지 않았다면 새로운 선을 다시 저장하고, 총 이동거리를 업데이트한다.
충돌하였다면 충돌 최소 거리를 더한 최종값을 반환한다.
import sys
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
L = int(input())
N = int(input())
MAX = L*2+1
next_dir = { 'L' : 1, 'R' : -1, 'S' : 0 }
rotate_list = [input().split() for _ in range(N)]
rotate_list.append((MAX, 'S'))
line_list = [(-L-1, -L-1, L+1, -L-1, 0),
(-L-1, L+1, L+1, L+1, 0),
(-L-1, -L-1, -L-1, L+1, 1),
(L+1, -L-1, L+1, L+1, 1)]
def find_crash(x, y, ax, ay, r) :
_line_list = line_list if len(line_list) == 4 else line_list[1:]
result = MAX
for idx, (sx, sy, ex, ey, dir) in enumerate(_line_list) :
if r % 2 == dir % 2:
if x == ax == sx :
min_y, max_y = min(sy, ey), max(sy, ey)
if min_y <= ay <= max_y or min(y, ay) <= min_y < max(y, ay):
dist = min_y - y if y < ay else y - max_y
result = min(result, dist)
elif y == ay == sy :
min_x, max_x = min(sx, ex), max(sx, ex)
if min_x <= ax <= max_x or min(x, ax) <= min_x <= max(x, ax):
dist = min_x - x if x < ax else x - max_x
result = min(result, dist)
else :
if sx == ex :
min_x, max_x = min(x, ax), max(x, ax)
min_y, max_y = min(sy, ey), max(sy, ey)
if min_x <= sx <= max_x and min_y <= y <= max_y :
result = min(result, abs(x - sx))
elif sy == ey :
min_y, max_y = min(y, ay), max(y, ay)
min_x, max_x = min(sx, ex), max(sx, ex)
if min_y <= sy <= max_y and min_x <= x <= max_x :
result = min(result, abs(y - sy))
return result if result < MAX else 0
def solve() :
cnt = 0
x, y, r = 0, 0, 0
for t, dir in rotate_list :
t = int(t)
ax, ay = x + dx[r]*t, y + dy[r]*t
is_crash = find_crash(x, y, ax, ay, r)
if is_crash :
cnt += is_crash
return cnt
cnt += t
line_list.insert(0, (x, y, ax, ay, r))
x, y, r = ax, ay, ( r + next_dir[dir] ) % 4
return cnt
print(solve())
