3190_뱀

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

3190번: 뱀

 

 

뱀이 사과를 먹고 길어져서 벽에 부딪히거나 하면 끝나는 게임이다. 다들 한번쯤 해본 적 있을 것이다.

 

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

문제에서 해당 멘트를 제공해 주는데 정말 코드로 구현하기 쉽게 힌트를 준셈과 같다. 위 말을 그대로 구현하기만 하면 된다.

 

다만 헷갈릴만한 점이 여러가지가 있다.

 

1. 뱀의 동선이 절대적 시간으로 주어진다는거 (게임이 시작하고 8초 D ,10초 D라면 실제로는 8초직진후 우회전, 2초 추가로 더 직진후 우회전이란 말)

2. 행,열이 0이 아닌 1부터 시작 ( 필자같은경우 n*n판으로 만들어서 1행 1열에 넣어야하는 값이면 0행 0열에 넣어야 했다.)

 

 

문제케이스에서 최대 10000번이라고 주었기에 10000번을 반복하도록 하면서 뱀을 큐에 넣고 빼면서 구현하였다. 즉 큐 안에 뱀의 머리 - 꼬리로 이어지는 좌표들을 넣고 관리하였다.

 

방향은 dx,dy 를 사용해서 D를 만나면 우회전, L을 만나면 좌회전이 되도록 구현하였다.

 

import sys
from collections import deque
input = sys.stdin.readline

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

n = int(input())
k = int(input())
board = [ [0]*n for _ in range(n) ]

for _ in range(k):
    a,b = map(int,input().split())
    board[a-1][b-1] = -1

l = int(input())
dic = {}
for _ in range(l):
    a,b = map(str,input().split())
    dic[int(a)] = b

board[0][0] = 1
snail = deque([[0,0]])
To = 0


for i in range(1,10000):

    y,x = snail[0]
    nx,ny = x + dx[To], y + dy[To]

    if 0<=nx<n and 0<= ny < n:
        if board[ny][nx] == 1:
            print(i)
            break
        elif board[ny][nx] == -1:
            board[ny][nx] = 1
            snail.appendleft([ny,nx])
        else:
            snail.appendleft([ny,nx])
            board[ny][nx] = 1
            a,b = snail.pop()
            board[a][b] = 0
    else:
        print(i)
        break

    if i in dic:
        if dic[i] =='D':
            To = (To+1)%4
        else:
            To = (To-1)%4