문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
문제 풀이
먼저 맵에서 아무 것도 없으면 0, 사과가 있으면 1, 뱀이 있으면 2로 표현을 했다.
일단 뱀이 벽이나 몸에 부딪히지 않는한 계속 움직여야 하기 때문에 while문을 사용했고, 뱀이 현재 어디에 위치해 있는지 알아야 몸에 부딪히는지 아닌지 알 수 있기 때문에 body를 추가했다.
또한 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향으로 회전하는 것도 구현해야 했으므로, [동, 남, 서, 북]으로 방향을 정하고, rotate_info를 사용하여 방향을 구하는 방법을 사용했다.
예를 들어 왼쪽 회전시 -> (rotate_info - 1) % 4 를 해주고 오른쪽 회전시 -> (rotate_info + 1) % 4 를 해줬다.
4로 나눈 나머지를 구하는 이유는 rotate_info가 0미만 or 4이상이 되었을때 0 ~ 3 사이의 값을 구해주기 위함
- ex) 동쪽 일때 왼쪽 회전 -> rotate_info가 0에서 -1 -> 4로 나눈 나머지는 3 -> 3번째 인덱스 값은 북쪽
- ex) 북쪽 일때 오른쪽 회전 -> roatate_info 3에서 4 -> 4로 나눈 나머지는 0 -> 0번째 인덱스 값은 동쪽
이후에는 게임이 종료되는 조건이 아닌 한 사과가 있을 경우, 사과가 없을 경우를 구현해주면 된다.
def solution(x, y, L):
# (x,y) -> 뱀의 머리 위치
Map[x][y] = 2 # 뱀이 있으면 : 2
rotate_info = 0
body = [(0, 0)] # 뱀의 전체 위치
time = 0
indices = 0
while True:
if indices < L and time == int(info[indices][0]):
if info[indices][1] == "L":
rotate_info -= 1
rotate_info %= 4
elif info[indices][1] == "D":
rotate_info += 1
rotate_info %= 4
indices += 1
time += 1
nx = x + dx[rotate_info]
ny = y + dy[rotate_info]
if nx >= 0 and nx <= n - 1 and ny >= 0 and ny <= n - 1:
# 사과가 있을 경우
if Map[nx][ny] == 1:
Map[nx][ny] = 2
body.append((nx, ny))
x, y = nx, ny # 뱀 머리 위치 갱신
# 사과가 없을 경우
elif Map[nx][ny] == 0:
Map[nx][ny] = 2
body.append((nx, ny))
a, b = body.pop(0) # 꼬리 이동
Map[a][b] = 0 # 꼬리 비우기
x, y = nx, ny # 뱀 머리 위치 갱신
# 꼬리와 부딪힌 경우
elif Map[nx][ny] == 2:
return time
else:
return time
if __name__ == "__main__":
n = int(input())
k = int(input())
# 보드
Map = [[0] * n for _ in range(n)]
for _ in range(k):
a, b = map(int, input().split())
Map[a - 1][b - 1] = 1 # 사과 : 1, 빈칸 : 0
# 방향전환
info = []
L = int(input())
for _ in range(L):
a, b = input().split()
info.append((a, b))
# 동,남,서,북
dx = [0, 1, 0, -1] # 행
dy = [1, 0, -1, 0] # 열
print(solution(0, 0, L))