문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
풀이
이 문제를 풀기 위해서 해결해야할 문제는 크게 세가지 정도라고 할 수 있겠다.
- 주어진 커맨드에 따라 뱀의 이동을 제어한다.
1-1. 커맨드에서 주어진 시간 정보를 통해 방향을 바꿀 타이밍을 구한다.
1-2. 방향을 제어한다. - 이동하면서 변하는 뱀의 길이, 위치를 그래프에 표시한다.
2-1. 사과를 먹으면 꼬리를 없앨 필요가 없다.
2-2. 사과를 먹지 않으면 길어지지 않기 때문에 현재 뱀 길이의 제일 마지막 값을 없애줘야 한다. (경로 저장 필요) - 최종적으로 커맨드를 다 입력해도 게임이 끝나지 않는 경우에 방향을 유지하면서 게임이 끝나는 시간을 구해준다.
1-1번을 해결하기 위해서 commands라는 deque를 만들고 미리 change_timing, command라는 변수를 while에 들어가기 전에 popleft로 뽑아주고 while을 돌면서 time이 change_timing과 일치할 때 방향을 바꿔주고 commands에 남은 값이 있다면 다시 popleft를 통해 변수들을 초기화 해주었다.
1-2는 directions라는 테이블에 4방향 이동 정보를 담고 동쪽 서쪽 이동에 유리하게 값들을 위치시키고
오른쪽은 아래와 같이 cur_direction이 4이상이면 0이 되도록 설정하고 1씩 증가시켜서 오른쪽으로 돌 수 있도록 설정하였고
cur_direction = cur_direction +1 if cur_direction + 1 < 4 else 0왼쪽은 0보다 작아지면 3이 되도록 설정하고 1씩 감소시켜서 왼쪽으로 돌 수 있도록 설정하였다.
cur_direction = cur_direction - 1 if cur_direction - 1 >= 0 else 32번을 해결하기 위해서 경로인 path deque를 따로 만들어 이동할 때 마다 담아두고 만약 사과를 먹었다면 그냥 진행하고 사과가 없는 곳으로 이동했다면 popleft를 통해 먼저 들어간 값 그러니까 지금 뱀의 머리와 가장 먼 값을 빼주는 방식으로 구현을 했다.
마지막으로 3번은 처음 문제를 풀 때 while문을 commands가 있을때까지 조건으로 해둔 탓에 계속 틀려서 고민해보니 커맨드가 끝이나도 게임이 끝나지는 않겠다라는 생각이 들어서 while문을 밑에 하나 더 추가해보니 맞았고 리팩터링을 통해서 뱀의 이동은 계속되고 change_timing값으로 제어하는 방식으로 변경했다.
from collections import deque
import sys
input = sys.stdin.readline
def change_location(cur_row:int, cur_col:int) -> None:
if maps[cur_row][cur_col] == 0:
path.append((cur_row, cur_col))
last_row, last_col = path.popleft()
maps[last_row][last_col] = 0
elif maps[cur_row][cur_col] == 1:
path.append((cur_row, cur_col))
maps[cur_row][cur_col] = "s"
def rotate_direction(cur_direction:int , command:str):
if command == "D":
cur_direction = cur_direction +1 if cur_direction + 1 < 4 else 0
else: cur_direction = cur_direction - 1 if cur_direction - 1 >= 0 else 3
return cur_direction
def is_wall(cur_row:int, cur_col:int) -> bool:
return 0 > cur_row or cur_row >= N or 0 > cur_col or cur_col >= N
def is_snake_body(cur_row:int, cur_col:int) -> bool:
return maps[cur_row][cur_col] == "s"
def get_end_time(cur_direction:int, time:int, cur_row:int, cur_col:int) -> int:
maps[cur_row][cur_col] = "s"
path.append((cur_row,cur_col))
change_timing, command = commands.popleft()
while True:
cur_row += directions[cur_direction][0]
cur_col += directions[cur_direction][1]
if is_wall(cur_row, cur_col):
return time + 1
if is_snake_body(cur_row, cur_col):
return time + 1
change_location(cur_row ,cur_col)
time+=1
if change_timing == time:
cur_direction = rotate_direction(cur_direction, command)
if commands:
next_timing, command = commands.popleft()
change_timing = next_timing
if __name__ == "__main__":
N = int(input())
maps = [[0] * N for _ in range(N)]
directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]
path = deque()
apple_cnt = int(input())
for _ in range(apple_cnt):
row, col = map(int, input().split())
maps[row-1][col-1] = 1
command_cnt = int(input())
commands = deque()
for _ in range(command_cnt):
second, command = input().split()
second = int(second)
commands.append((second, command))
print(get_end_time(cur_direction=2, cur_row=0, cur_col=0, time=0))