[1] BOJ3190 - 뱀

[robert-min]

문제 추천 이유!!

• 문제 조건을 하나씩 구현하면서 푸는 전형적인 구현 문제
• 구현 문제 연습으로 추천

문제 링크

https://www.acmicpc.net/problem/3190

*작성가이드 입니다.

1. 작성자가 먼저 문제를 풀어봅니다.
2. 문제를 풀고나서 난이도를 설정합니다.
   • 1 : 30분 이내로 손 쉽게 풀 수 있음
   • 2 : 1시간 이내로 고민하면 풀 수 있음
   • 3 : 1시간 이상 걸리거나 어려움
3. Coding test Basic template을 사용하여 이슈를 생성합니다.
   • 제목은 : [난이도] 문제명으로 작성합니다.
   • 내용은 : 문제 링크만 추가하세요
   • 문제 사이트를 label로 추가해주세요. 기본값은 백준
4. 문제 풀이는 이슈의 코멘트로 추가해주세요
   • 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
   • 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!
5. 다른 사람에게 채팅으로 직접 문제를 추천하세요.
   • 디스코드 채널을 통해 다른 모임원에게 문제를 추천
   • 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : 30분 🗂️ 유형 :구현

🖌️ 문제 풀이

• 문제 조건 정리
• 매 시간 마다 이동(while) time += 1
  1. 머리를 현재 바라보고 있는 칸으로 이동
  2. 이동했을 때, matrix 밖 또는 자기 몸(visited)에 부딪히면 끝
  3. 이동했을 때, 사과 O >> 꼬리 그대로 / 사과 X >> 꼬리 줄이기
     • visited 가장 먼저 들어온 값 삭제 >> Q
  4. time == orders[] 인 경우 방향 변경
     • L은 왼쪽, D는 오른쪽으로 90도
     • 위, 오른, 아래, 왼
     • D일 경우 +1, L일 경우 -1
     • <0 >> 3, 4> >> 0 으로

"""
Return : 게임이 몇 초에 끝나는지

매 시간 마다 이동(while) time += 1
1. 머리를 현재 바라보고 있는 칸으로 이동
2. 이동했을 때, matrix 밖 또는 자기 몸(visited)에 부딪히면 끝
3. 이동했을 때, 사과 O >> 꼬리 그대로 / 사과 X >> 꼬리 줄이기
    - visited 가장 먼저 들어온 값 삭제 >> Q
4. time == orders[] 인 경우 방향 변경
    - L은 왼쪽, D는 오른쪽으로 90도
    - 위, 오른, 아래, 왼
    - D일 경우 +1, L일 경우 -1
    - <0 >> 3, 4> >> 0 으로
Return : time
"""
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
matrix = [[0] * N for _ in range(N)]
K = int(input())
for _ in range(K):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    matrix[x][y] = 1

orders = deque([])
L = int(input())
for _ in range(L):
    time, direct = input().split()
    orders.append((int(time), direct))

def change_dir(now_dir, dir):
    if dir == "L":
        now_dir -= 1
    elif dir == "D":
        now_dir += 1
    if now_dir < 0:
        now_dir = 3
    elif now_dir == 4:
        now_dir = 0
    return now_dir

time = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

x, y = 0, 0
Q = deque([(0, 0)])
visited = [[0] * N for _ in range(N)]
visited[0][0] = 1

now_dir = 1   # 오른쪽
while True:
    time += 1
    nx = x + dx[now_dir]
    ny = y + dy[now_dir]

    #  matrix 밖
    if nx < 0 or ny < 0 or nx >= N or ny >= N:
        break

    # 자기 몸(visited)에 부딪
    if (nx, ny) in Q:
        break

    # 사과 O >> 꼬리 줄이기
    if matrix[nx][ny] == 1:
        matrix[nx][ny] = 0
    else:
        Q.popleft()

    # time == orders[] 인 경우 방향 변경
    if orders and time == orders[0][0]:
        _, dir = orders.popleft()
        now_dir = change_dir(now_dir, dir)

    visited[nx][ny] = 1
    Q.append((nx, ny))
    x, y = nx, ny

print(time)