3190번 - 뱀

문제

3190번: 뱀 (acmicpc.net)

3190번: 뱀

풀이 1

뱀의 머리가 벽 또는 자신의 몸에 닿으면 프로그램이 종료되어야 하므로, deque에 뱀이 차지하고 있는 좌표들을 넣는것이 핵심이다. 또한 보드의 크기가 최대 100까지로 제한되어 있는 것에 착안하여 뱀을 1초 씩 이동시키며 주어진 조건을 확인 하는 완전탐색의 방법이 유효하다는 것을 알 수 있다. 처음에 입력된 방향 변환 정보를 모두 사용하고, 이후로는 방향 전환이 없으므로 바라보고 있는 방향으로 직진하여 벽 또는 자신의 몸이 나타날 때 까지 시간을 1초씩 증가시킨다. 뱀이 가는 방향은 역시 회전변환을 사용했다.

from collections import deque

n = int(input())
board = [[1]*(n+2)] + [([1] + [0]*n + [1]) for _ in range(n)] + [[1]*(n+2)]
board[1][1] = 1

k = int(input())
for _ in range(k):
  row,col = map(int, input().split())
  board[row][col] = 9

l = int(input())
moves = []
for _ in range(l):
  sec,head = input().split()
  moves.append((int(sec),head))

def rotate_head(vector, r):
  row,col = vector
  return (-col, row) if r == 'L' else (col, -row)

time = 0
vector = (0,1)
head,tail = [1,1],[1,1]
moves = deque(moves)
snake = deque()
snake.append((1,1))

try :
  while moves:
    t,r = moves.popleft()
    for _ in range(t-time):
      time += 1
      nRow = snake[0][0]+vector[0]
      nCol = snake[0][1]+vector[1]
      if board[nRow][nCol] == 1:
        raise Exception(time)
      if board[nRow][nCol] != 9:
        board[snake[-1][0]][snake[-1][1]] = 0
        snake.pop()
      snake.appendleft((nRow,nCol))
      board[snake[0][0]][snake[0][1]] = 1
    vector = rotate_head(vector,r)
except Exception as e:
  print(e)
else:
  while board[snake[0][0]+vector[0]][snake[0][1]+vector[1]] != 1:
    time += 1
    snake.pop()
    snake.appendleft((snake[0][0]+vector[0],snake[0][1]+vector[1]))
  print(time+1)

풀이 2

핵심 아이디어는 뱀을 큐로 구현하는 것이다. 꼬리는 머리가 움직이는 방향대로만 따라가므로 큐로 구현 가능하다는 것을 알 수 있다. 또한 주의할 점은 머리 바로 다음칸에 "현재 시점에서"의 몸통이 있다면, 그대로 프로그램을 종료해야한다는 것이다.

from collections import deque

# 동,남,서,북
dRow = [0,1,0,-1]
dCol = [1,0,-1,0]

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


def get_answer():
    L = int(input())
    time = 0
    snake = deque()
    snake.append((1,1))
    dir = 0
    for _ in range(L):
        X,C = input().split()
        X = int(X)
        # 현재시간 ~ X초 까지 직진
        for t in range(X-time):
            # 시간 갱신
            time += 1
            # 뱀 머리
            r,c = snake[-1]
            nr,nc = r+dRow[dir],c+dCol[dir]
            # 만약 다음칸이 벽이거나, 몸이면
            if not (1 <= nr <= N and 1 <= nc <= N) or (nr,nc) in snake:
                return time
            # 사과가 아니면
            if board[nr][nc] != 1:
                snake.popleft()
            else:
                board[nr][nc] = 0
            snake.append((nr,nc))
        # 방향 전환
        if C == 'L':
            dir = (dir+3)%4
        else:
            dir = (dir+1)%4
    # 방향 전환이 끝난 뒤, 벽이나 몸에 닿을 때 까지 직진
    while True:
        # 시간 갱신
        time += 1
        # 뱀 머리
        r,c = snake[-1]
        nr,nc = r+dRow[dir],c+dCol[dir]
        # 만약 다음칸이 벽이거나, 몸이면
        if not (1 <= nr <= N and 1 <= nc <= N) or (nr, nc) in snake:
            return time
        # 사과가 아니면
        if board[nr][nc] != 1:
            snake.popleft()
        else:
            board[nr][nc] = 0
        snake.append((nr, nc))


print(get_answer())