[파이썬] 백준 3190 뱀

[파이썬] 백준 3190 뱀

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

 

문제

Dummy라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데 , 사과를 먹으면 뱀 길이가 늘어난다.

뱀이 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝이 난다.

 

N x N 정사각 보드 위에서 진행되고 몇몇 칸에 사과가 놓여 있다. 보드 상하좌우 끝에는 벽이 있다.

뱀의 처음 시작위치는 맨 위 맨 좌측에 위치하고 처음 길이는 1이다. 뱀은 처음에는 오른쪽으로 향한다.

 

뱀은 매초 마다 움직이는데 아래의 규칙을 따른다.

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

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

 

입력

첫 번째 줄에 보드 크기 N

두 번째 줄에 사과의 개수 K

다음 K개의 줄에는 사과의 위치가 (행, 열) 위치로 지로 주어진다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다.

다음 L 개의 줄에는 뱀의 방향 변환 정보가 정수 X 와 문자 C로 주어지는데

게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')으로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

 

출력

첫째 줄에 게임이 몇 초에 끝나지는지 출력한다.

 

풀이

사과의 위치를 담을 배열, 뱀의 움직일 정보를 담을 배열, 뱀의 위치하는 칸을 담을 배열 이렇게 총 3개의 배열을 이용하였다.

여기서 뱀의 움직임을 담을 배열과 뱀의 위치를 담을 배열은 deque를 사용하였다.

그 이유는 밴의 움직일 정보를 담을 배열에서 값을 순서대로 꺼내는데 list 보다는 deque가 편하다고 생각되었고

뱀의 위치 또한 머리가 움직일 때마다 머리 부분을 배열의 맨 앞으로 꺼내서 뱀의 길이나 꼬리의 길이를 삭제를 쉽게 하려고 deque를 사용하였다.

time, v = array.popleft() if array else (float('inf'), None)
now=0
case=0
dx=[0,1,0,-1]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
dy=[1,0,-1,0]

뱀의 방향에 따라 이렇게 4개의 케이스를 만들었으면 now 현재 시간을 의미한다.

time , v는 움직일 시간, 방향 정보를 담았다.

    nx=x+dx[case]
    ny=y+dy[case]
	#q는 뱀위 위치를 담을 배열
    if(0<=nx<n and 0<=ny<n and (nx,ny) not in q):

        if [nx,ny] in apples: #사과있는경우
            q.appendleft((x,y))
            q.appendleft((nx,ny))
            re=apples.index([nx,ny])
            del apples[re]
            now+=1
        else: #사과거 없는경우 가장 마지막 제거
            if(len(q)>0):
                q.appendleft((x, y)) # 현재 위치 넣기
                q.pop() # 꼬리 제거 하기

            q.appendleft((nx,ny)) # 이동한 위치 넣기
            now += 1
    else:
        now+=1
        break

nx와 ny는 NxN 내부에 있어야 하고 새로 이동한 머리가 자기 자신의 위치에 있으면 안 되기에  뱀의 위치 정보가 담기 배열인 q에 현재 이동한 nx와 ny가 있는지 확인하는 조건을 추가하였다.

그 후 이동한 위치에 사과가 있다면 이동하기 전에 위치를 다시 맨 앞에 넝어주고 이동한 위치 또한 맨앞에 넣어준다.

그 후 현재 그 위치의 사과는 삭제한다.

 

사과가 없을 경우는 몸통의 길이를 유지해야 하기에 이동하기 전 위치를 넣고 꼬리를 빼준다.

그리고 이동한 위치도 맨 앞으로 넣어준다.

 

이렇게 값을 넣고 난 후 모든 경우에 시간을 1초씩 더해준다 

 

    if now==time:

        if(case==0):
            if v=="L":
                case=3
            else:
                case=1
        elif case==1:
            if v=="L":
                case=0
            else:
                case=2
        elif case==2:
            if v=="L":
                case=1
            else:
                case=3
        elif case==3:
            if v=="L":
                case=2
            else:
                case=0
        if array:
            time, v = array.popleft()
        else:
            time = float('inf')

이동하고 난 후 방향을 바꿔야 할 시간하고 같아지면 조건에 맞게 방향을 case를 바꾸어서 어떻게 이동할지 바꿔줄 수 있다.

전체 코드 

import sys
from collections import deque

input = sys.stdin.readline

n=int(input())
k=int(input())

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


array=deque()
l =int(input())
for i in range(l):
    time, direction = input().split()
    array.append((int(time), direction))

q=deque()
q.append((0,0))
time, v = array.popleft() if array else (float('inf'), None)
now=0
case=0
dx=[0,1,0,-1]
dy=[1,0,-1,0]
while(q):
    x,y=q.popleft()


    nx=x+dx[case]
    ny=y+dy[case]

    if(0<=nx<n and 0<=ny<n and (nx,ny) not in q):

        if [nx,ny] in apples: #사과있는경우
            q.appendleft((x,y))
            q.appendleft((nx,ny))
            re=apples.index([nx,ny])
            del apples[re]
            now+=1
        else: #사과거 없는경우 가장 마지막 제거
            if(len(q)>0):
                q.appendleft((x, y)) # 현재 위치 넣기
                q.pop() # 꼬리 제거 하기

            q.appendleft((nx,ny)) # 이동한 위치 넣기
            now += 1
    else:
        now+=1
        break


    if now==time:

        if(case==0):
            if v=="L":
                case=3
            else:
                case=1
        elif case==1:
            if v=="L":
                case=0
            else:
                case=2
        elif case==2:
            if v=="L":
                case=1
            else:
                case=3
        elif case==3:
            if v=="L":
                case=2
            else:
                case=0
        if array:
            time, v = array.popleft()
        else:
            time = float('inf')

print(now)