https://www.acmicpc.net/problem/10875
10875번: 뱀
가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는
www.acmicpc.net
문제
가로 길이와 세로 길이가 모두 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 ≤ 108)이 주어진다. 두 번째 줄에는 머리의 방향을 몇 번 회전할 것인지를 나타내는 정수 N(0 ≤ N ≤ 103)이 주어진다. 다음 N 개의 줄에 뱀이 머리를 어떻게 회전하는지에 대한 정보가 주어진다. i(1 ≤ i ≤ N)번째 줄에 정수 ti(1 ≤ ti ≤ 2 · 108)와 diri 가 차례로 주어지며 diri 는 문자 L, 또는 R 중 하나이다. 뱀은 i = 1인 경우 출발, 그 외의 경우엔 i − 1번째 회전으로부터 ti 초 후에 diri 의 방향으로 머리를 회전하며, 만일 diri 가 L 이라면 왼쪽 (반시계방향)으로, R 이라면 오른쪽 (시계방향)으로 90도 회전한다.
출력
첫 번째 줄에 답을 나타내는 값을 하나 출력한다. 이 값은 뱀이 출발한지 몇 초 후에 숨을 거두는지를 나타낸다.
우선 L 범위가 10^8이다. 뱀의 모든 위치를 일일이 체크하면 시간초과 당할게 뻔하다.
뱀이 움직인 후 회전을 하기 직전 위치를 저장해야한다.
뱀이 동서쪽으로 이동한 좌표는 수평의 선분으로, 뱀이 남북쪽으로 이동했다면 수직의 선분으로 저장하는 것이 좋다.
문제 풀면서 고려해봐야할 것은 아래 4가지다.
1. 뱀이 자기 꼬리에 박치기 하는 경우
2. 벽에 부딪히는 경우
3. 몸에 부딪히는 경우
4. 모든 회전을 다 한 경우(직선 하다가 몸 또는 벽에 부딪힘)
위 조건 중에서도 3번을 깊게 고려하지 못해서 틀리는 경우가 많다. 나도 그랬고 질문게시판에 있는 사람들도 그런 것 같았다.
몸에 부딪히는 경우를 고려해서 동서쪽으로 가는 방향이면 수직 선분을 비교해주고, 남북쪽으로 이동하는 경우라면 수평 선분과 비교해주면 된다. 그런데 이떄 주의할 점이 있다.
비교해주는 선분 중 뱀과 가장 먼저 닿는 선분인가를 고려해줘야한다.
또한 만약 북쪽으로 이동 중인 뱀이라면 뱀이 이동하기 이전의 위치보다 위쪽에 위치한 수평 선분들, 그리고 그 수평 선분들 중에서도 뱀의 현재 x좌표가 그 수평 선분 안에 포함되는지를 확인해야한다.
이후 모든 조건이 충족된 수평 선분이 나왔다면 뱀이 이동한 위치가 해당 수평 선분을 넘어섰는지 체크하면 된다.
만약 수평 선분을 넘어섰다면 뱀은 그대로 죽는 것이고, 아니면 이어서 진행해주면 된다.
코드
# 몸에 부딪히는 경우 가장 먼저 부딪히는 몸 찾기
def find_nearest(cur_direction, prevX, prevY):
min_dist, min_snake = 3*L, 2*L
if cur_direction == 0:
for i, snake in enumerate(ver_x):
if prevX < snake: # 이전 위치보다 오른쪽에 있는 몸들 중
if min_dist > abs(snake - prevX) > 0:
# 그리고 y범위 안에 있다면
y1, y2 = ver_y[i][0], ver_y[i][1]
if y1 <= prevY <= y2:
min_dist = abs(snake - prevX)
min_snake = snake
if cur_direction == 2:
for i, snake in enumerate(ver_x):
if prevX > snake: # 이전 위치보다 왼쪽에 있는 몸들 중
if min_dist > abs(snake - prevX) > 0:
# 그리고 y범위 안에 있다면
y1, y2 = ver_y[i][0], ver_y[i][1]
if y1 <= prevY <= y2:
min_dist = abs(snake - prevX)
min_snake = snake
elif cur_direction == 1:
for i, snake in enumerate(hor_y):
if prevY < snake: # 이전 위치보다 위에 있는 몸들 중
if min_dist > abs(snake - prevY) > 0:
# 그리고 x 범위 안에 있다면
x1, x2 = hor_x[i][0], hor_x[i][1]
if x1 <= prevX <= x2:
min_dist = abs(snake - prevY)
min_snake = snake
elif cur_direction == 3:
for i, snake in enumerate(hor_y):
if prevY > snake: # 이전 위치보다 아래에 있는 몸들 중
if min_dist > abs(snake - prevY) > 0:
# 그리고 x 범위 안에 있다면
x1, x2 = hor_x[i][0], hor_x[i][1]
if x1 <= prevX <= x2:
min_dist = abs(snake - prevY)
min_snake = snake
return min_snake
def snakeGame(cur_direction, cur_x, cur_y, time):
while True:
if moves:
t, nxt_direction = moves.pop(0)
else:
nxt_direction = False
# 동쪽으로 이동
if cur_direction == 0:
prev_x = cur_x
prev_y = cur_y
cur_x = prev_x + t
# 가장 먼저 부딪힌 몸 찾기
min_snake_x = find_nearest(cur_direction, prev_x, prev_y)
# 꼬리에 박치기 하는 경우(동쪽으로 가는 경우에만 있는 특이 케이스)
if cur_y == 0 and prev_x < 0 and cur_x >= 0 and min_snake_x > 0:
ans = time - prev_x
return ans
if min_snake_x != 2*L:
if cur_x >= min_snake_x:
ans = time + abs(prev_x - min_snake_x)
return ans
# 경계를 벗어났다면
if cur_x > L:
ans = time + L - prev_x
return ans + 1
hor_x.append((prev_x, cur_x))
hor_y.append(cur_y)
# 서쪽으로 이동
elif cur_direction == 2:
prev_x = cur_x
prev_y = cur_y
cur_x = prev_x - t
# 가장 먼저 부딪힌 몸 찾기
min_snake_x = find_nearest(cur_direction, prev_x, prev_y)
if min_snake_x != 2*L:
if cur_x <= min_snake_x:
ans = time + prev_x - min_snake_x
return ans
# 경계를 벗어났다면
if cur_x < -L:
ans = time + abs(L + prev_x)
return ans + 1
hor_x.append((cur_x, prev_x))
hor_y.append(cur_y)
# 북쪽으로 이동
elif cur_direction == 1:
prev_x = cur_x
prev_y = cur_y
cur_y = prev_y + t
# 몸에 부딪혔다면
min_snake_y = find_nearest(cur_direction, prev_x, prev_y)
if min_snake_y != 2*L:
# 현재 y값이 몸을 통과했다면
if cur_y >= min_snake_y:
ans = time + min_snake_y - prev_y
return ans
# 경계를 벗어났다면
if cur_y > L:
ans = time + L - prev_y
return ans + 1
ver_x.append(cur_x)
ver_y.append((prev_y, cur_y))
# 남쪽으로 이동
elif cur_direction == 3:
prev_x = cur_x
prev_y = cur_y
cur_y = prev_y - t
# 몸에 부딪혔다면
min_snake_y = find_nearest(cur_direction, prev_x, prev_y)
if min_snake_y != 2*L:
if cur_y <= min_snake_y:
ans = time + prev_y - min_snake_y
return ans
# 경계를 벗어났다면
if cur_y < -L:
ans = time + abs(prev_y + L)
return ans + 1
ver_x.append(cur_x)
ver_y.append((cur_y, prev_y))
time+=t
# 방향 전환
if nxt_direction == 'L':
cur_direction = (cur_direction+1) % 4
elif nxt_direction == 'R':
cur_direction = (cur_direction-1) % 4
if __name__ == '__main__':
L=int(input())
n=int(input())
if n==0:
print(L+1)
else:
moves = []
for i in range(n):
a,b = map(str,input().split())
moves.append((int(a), b))
# 수평으로 움직이는 몸과 수직으로 그려지는 몸 리스트
hor_x, hor_y, ver_x, ver_y = [], [], [], []
ans = snakeGame(0,0,0,0)
print(ans)구현 진짜 너무 빡센거같다.
다음에는 세그먼트 트리 알고리즘 배워서 문제 좀 풀어볼 생각이다.
'알고리즘 > 구현' 카테고리의 다른 글
| [Python] 백준 17143 - 낚시왕 (0) | 2023.02.08 |
|---|---|
| [Python] 백준 3190 - 뱀 (0) | 2023.02.06 |