😲 문제
출처
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.입력 6 3 3 4 2 5 5 3 3 3 D 15 L 17 D출력 9
❗️ 문제 재정의
뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다.
뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
종료조건 : 벽 또는 자기자신의 몸과 부딪혔는가?
뱀의 첫 위치 : 0,0
뱀 초기 이동 위치(머리의 진행 방향) : 오른쪽
몸이 늘어나는 방식 : 몸을 늘려 다음칸에 위치
사과를 먹는다면 : 사과는 사라지고 꼬리는 움직이지 않는다.(몸의 길이가 늘어남)
사과가 없다면 : 꼬리를 지운다. 앞으로 나아가기에 그렇다.
어려운 것이 어떤 것일까?
머리의 진행 방향 설정이다.
- 머리가 회전하면 진행방향의 기준이 달라짐.
- 진행 방향의 기준이 달라지면 열 또는 행을 더할 때 바뀌어진 기준에 따라 더해야함.
✔ 계획 수립
- 머리의 방향을 바꾸어야 하는 초인가?
- 맞다면 머리를 해당 방향에 놓는다. ( 딕셔너리로 구현하기 )
- 머리 방향과 상관 없이 뱀의 진행 방향으로 한 칸 전진 (queue.appendleft())
- 전진한 곳이 안전한 영역인가? (몸에 부딫히지 않거나 범위 안쪽 이여야함)
- 전진한 곳에 사과가 있는가?
- 꼬리를 지우지 않는다.
- 전진한 곳에 사과가 없는가?
- 꼬리를 자른다. (queue.pop())
- 전진한 곳에 사과가 있는가?
👨🏻💻 문제 풀이
from collections import deque
import sys
input = sys.stdin.readline
# ---- 입력 ---- #
n = int(input()) # 맵의 크기
k = int(input()) # 사과이 개수
apple_list = [list(map(int,input().split())) for _ in range(k)]
l = int(input())
move_list = [list(input().split()) for _ in range(l)]
# ---- 초기화 ---- #
snake = deque()
graph =[[0] * n for _ in range(n)]
graph[0][0] = 1
for r, c in apple_list:
graph[r-1][c-1] = 4
cur_second = 0
head_loc = [0,0]
snake.append(head_loc)
head_dir = 0 # 처음 뱀의 머리 방향 (동쪽임)
dir_dict = {0:(0,1),1:(1,0),2:(0,-1),3:(-1,0)} # 머리를 오른쪽 회전 시 동남서북 , 머리를 왼쪽으로 회전 시 북서남동임.
eat_apple = False # 사과를 먹는다면 True 처리
check_ok = True # 범위를 벗어나지 않거나 몸에 부딫히지 않는다면 True
# ---- 안전구역 체크 함수 ---- #
def check_move(graph, n, loc):
r,c = loc[0],loc[1]
if 0<=r<n and 0<=c<n and graph[r][c] != 1:
return True
return False
# ---- 동작 ---- #
idx = 0 # 방문해야하는 방향 전환 리스트 위치(index)
while check_ok: # 멈출때까지 반복
if idx < len(move_list): # 방향 전환 리스트 순차 방문
moves = move_list[idx]
move_second = int(moves[0])
move_direction = moves[1]
if move_second == cur_second: # 현재 초가 방향 전환을 해야하는 초라면
# 회전 처리
if move_second == cur_second:
if move_direction == "L": # 왼쪽 회전임.
# 동 -> 북, 서 -> 남, 북 -> 서, 남 -> 동
# 머리의 방향을 변경한다.
head_dir = (head_dir - 1) % 4
else: # 오른쪽 회전임.
# 동 -> 남, 서 -> 북, 북 -> 동, 남 -> 서
head_dir = (head_dir + 1) % 4
idx+=1
# 변경된 방향 또는 원래 방향으로 한 칸 앞으로 이동한다.
head_loc = [head_loc[0] + dir_dict[head_dir][0], head_loc[1] + dir_dict[head_dir][1]]
if check_move(graph, n, head_loc):
if graph[head_loc[0]][head_loc[1]] == 4: # 사과가 있었다면 먹었다는 표시한다.(꼬리를 안자름)
eat_apple = True # 사과 먹음 처리
graph[head_loc[0]][head_loc[1]] = 1
snake.appendleft(head_loc) # 머리를 늘린다. 앞에서 추가함.
else: # 범위를 벗어나거나 몸에 부딫힘.
check_ok = False
break
# 사과를 먹엇다면 꼬리는 냅두기
# 안먹었다면 꼬리를 자르기
if eat_apple:
eat_apple = False # 다시 안먹음 처리
else:
tail = snake.pop()
graph[tail[0]][tail[1]] = 0
cur_second += 1
print(cur_second+1)😅 회고
필요한 변수의 개수가 문제를 풀면서 계속 늘어나서 약간 풀면서 불안한 감정이 들게 하는 문제였다.
충분히 최적화할 여지는 있었지만 기존 로직을 보면서 하였기에 변경하기가 힘들었다.
시작 위치가 1,1이라는 사실을 깜빡했다. 즉, 사과 또한 행과 열에 1이 각각 더해진 상태라는 의미이다.
뱀의 상태를 처음부터 queue로 두지 않아 다시 바꾸는데 시간이 소요되었다.ㅠ
