import sys
from collections import deque
n = int(sys.stdin.readline()) # 보드의 크기
k = int(sys.stdin.readline()) # 사과의 개수
apple = [list(map(int, sys.stdin.readline().split())) for _ in range(k)] # 사과의 위치
l = int(sys.stdin.readline()) # 방향 전환 횟수
change = []
for _ in range(l):
changeSec, changeDir = input().split()
changeSec = int(changeSec)
change.append([changeSec, changeDir]) # 초, 방향을 입력받되, 초는 int로 입력받는다
diList = ['' for _ in range(change[-1][0] + 1)] # 인덱스와 초를 동기화 하기 위해 + 1
for i in change:
diList[i[0]] = i[1] # di의 i번 인덱스가 초, i번의 데이터는 전환할 방향(L, D)
# 0, 1, 2, 3 => 북, 동, 남, 서
# whereCount % 4 의 값에 따라 방향을 전환한다
# whereCount 값은 D면 + 1 , L이면 - 1
# 0 -> x-1 / 1 -> y+1 / 2 -> x+1 / 3 -> y-1
whereCount = 1
sec = 0 # 결과 저장(초)
snake = deque()
snake.append((1,1)) # 시작 위치 저장
while True:
sec += 1
# 현재 방향에 따라 1칸 진행
if whereCount % 4 == 1:
if (snake[-1][0], snake[-1][1] + 1) in snake: # 자기자신과 부딪힌다면 탈락
break
else:
snake.append((snake[-1][0], snake[-1][1] + 1)) # 안 부딪히면 진행
elif whereCount % 4 == 2:
if (snake[-1][0] + 1, snake[-1][1]) in snake: # 자기자신과 부딪힌다면 탈락
break
else:
snake.append((snake[-1][0] + 1, snake[-1][1])) # 안 부딪히면 진행
elif whereCount % 4 == 3:
if (snake[-1][0], snake[-1][1] - 1) in snake: # 자기자신과 부딪힌다면 탈락
break
else:
snake.append((snake[-1][0], snake[-1][1] - 1)) # 안 부딪히면 진행
else:
if (snake[-1][0] - 1, snake[-1][1]) in snake: # 자기자신과 부딪힌다면 탈락
break
else:
snake.append((snake[-1][0] - 1, snake[-1][1])) # 안 부딪히면 진행
# 진행했는데 벽에 닿으면 탈락
if snake[-1][0] > n or snake[-1][0] <= 0 or snake[-1][1] > n or snake[-1][1] <= 0:
break
if list(snake[-1]) not in apple: # 사과가 없으면 꼬리를 자른다 (snake는 deque자료형이라 비교를 위해서 list로 변환)
snake.popleft()
else: # 사과를 먹으면 꼬리를 유지하고 사과를 없앤다
apple.remove(list(snake[-1]))
# diList 리스트는 마지막 방향전환 초 + 1 만큼의 길이이기 때문에, 현재 초가 더 길어지면 검사하지 않도록 한다.
if len(diList) > sec:
if diList[sec] == 'L':
whereCount -= 1
elif diList[sec] == 'D':
whereCount += 1
print(sec)
큐(덱)를 사용하는 문제이다. 뱀의 위치를 저장할 때 큐를 사용하여, append() 메소드로 진행하고 popleft() 메소드로 꼬리를 자른다.
뱀은 1,1 좌표에서 시작하고 초기 방향은 오른쪽이다. 1초에 1칸씩 진행하며, 정해진 초에 정해진 방향으로 전환해 가며 진행한다.
진행했는데 사과가 있으면 길이가 늘어나고, 사과가 없으면 그냥 진행한다.
진행했는데 자신의 몸통에 닿거나 벽에 닿으면 종료된다.
진행 시마다 sec(초)을 1씩 늘리며, 종료된 후 sec을 출력한다.
apple : 사과의 위치 리스트
diList : 초+방향 리스트이며 인덱스 번호가 "초"를 의미한다. 예시는 2초에 오른쪽으로 꺾게 된다. ex) ['', '', 'D']
- diList는 입력받은 마지막 방향 전환의 초 + 1 만큼의 길이이다.
- 만약 마지막 방향 전환이 17, 'D' 였을 경우 diList의 길이는 18이 된다.
- 따라서 마지막 조건문을 걸어서 18초 이상이 되었을 때부터 diList를 검사하지 않게 해야 한다.
whereCount : 전환할 방향을 설정할 변수이다.
0, 1, 2, 3 순서로 북, 동, 남, 서 방향으로 정의하였으며 우회전 시 + 1, 좌회전 시 - 1 을 한다.
이후 whereCount % 4 의 나머지 값을 구하면 0, 1, 2, 3 값중에 하나가 나오며 안정적으로 방향을 선택할 수 있다.
x,y 좌표가 n을 넘거나, 0과 같거나 작아지면 벽에 부딪힌 걸로 간주해 종료된다.
x,y 좌표가 몸통과 부딪히면 (snake 큐(덱)에 이미 존재하면) 자기 자신과 부딪힌 걸로 간주해 종료된다.