알고리즘/[Python] 백준

(Python) 백준 3190번 : 뱀

 

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

 

3190번: 뱀

문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따

www.acmicpc.net


 

(Python) 백준 3190번 뱀

(Python) 백준 3190번 : 뱀

  • 알고리즘 분류 :
    • 시뮬레이션

문제 설명

  • 뱀은 사과를 먹으면 길이가 1씩 증가한다.
  • 뱀이 벽 or 자신의 몸과 부딪히면 게임은 끝난다.
  • NxN 크기의 정사각 보드위에서 게임이 진행된다. 외곽은 벽으로 되어 있다.
  • 정사각 보드 위의 몇몇 칸에는 사과가 놓여져 있다.
  • 뱀의 첫 시작 위치는 맨위 맨왼쪽(1행 1열), 길이는 1, 방향은 오른쪽을 향한채로 시작한다.

뱀은 매 초마다 다음과 같은 규칙을 따라 이동한다.

  • 뱀은 먼저 몸길이를 늘려서 머리를 다음칸에 위치시킨다.
  • 이동한 칸에 사과가 있다 -> 사과 제거, 꼬리는 그대로.
  • 이동한 칸에 사과가 없다 -> 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

출력해야 하는 값
사과의 위치와 뱀의 이동경로가 주어진다.
이 게임은 몇 초에 끝나는가?


입력
보드의 크기 N (2<=N<=100)
사과의 개수 K (0<=K<=100)

K개의 줄에 사과의 위치가 주어진다. (행, 열) 위치
사과의 위치는 모두 다르며, 뱀이 처음 시작하는 위치엔 사과가 없다.

뱀의 방향 변환 횟수 L (1<=L<=100)
L개의 줄에 뱀의 방향 변환 정보가 주어진다.
게임 시작 시간으로부터 X초가 끝난 뒤 왼쪽으로 90도 회전이면 'L'이고, 오른쪽으로 90도 회전이면 'D'이다.
X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.


In [2]:
#import sys
from collections import deque
#input = sys.stdin.readline

N = int(input()) ## 보드 크기
K = int(input()) ## 사과 개수


## NxN의 board를 만든다.
board_array = [[1]*(N+2)] + [[1]+[0]*N+[1] for _ in range(N)] + [[1]*(N+2)]


for i in range(K):
    a,b = map(int, input().split()) ## a,b:사과 위치
    board_array[a][b] = 2 ## 사과는 숫자 2로 표현

    
L = int(input()) ## 뱀의 방향 변환 횟수
## 뱀의 방향 변환 정보
L_array = list(map(lambda x:[int(x[0]), x[1]], [input().split() for _ in range(L)]))
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
In [3]:
# board_array : 보드 맵
Out[3]:
[[1, 1, 1, 1, 1, 1, 1, 1],
 [1, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 2, 0, 1],
 [1, 0, 0, 0, 2, 0, 0, 1],
 [1, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 2, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 0, 0, 1],
 [1, 1, 1, 1, 1, 1, 1, 1]]
In [4]:
# L_array : 뱀의 방향 변환 정보 [정수타입, string타입]
Out[4]:
[[3, 'D'], [15, 'L'], [17, 'D']]
In [5]:
time = 0 ## 첫 시작은 일단 0초부터
x,y = 1,1 ## 뱀의 첫 위치
direction = {0:(-1,0), 1:(0,1), 2:(1,0), 3:(0,-1)} ## 0:북 1:동 2:남 3:서
d = 1 ## 현재 방향은 오른쪽 (동쪽)
snake_array = deque([[1,1]]) ## 뱀의 위치를 큐로 나타낸다.

## board_array -> 0:빈공간, 1:벽, 2:사과, 3:뱀
board_array[1][1] = 3 ## 처음 뱀이 (1,1)에 존재하므로

## 이동한 후에 뱀 머리의 위치가 벽이거나, 자신의 몸일 경우 stop
while(1):
    ## 일단 뱀의 머리를 이동시킨다. 바라보고 있는 방향으로.
    x = x + direction[d][0]
    y = y + direction[d][1]
    
    ## 이동한 곳에 사과가 있다.
    if board_array[x][y] == 2:
        board_array[x][y] = 3 ## 이제는 사과 대신 뱀의 머리가 위치한다.
        snake_array.append([x, y]) ## snake_array의 맨 오른쪽 원소가 머리, 왼쪽이 꼬리부분이다.
        time = time + 1
    ## 이동한 곳엔 사과가 없고, 그냥 빈 공간이다.
    elif board_array[x][y] == 0:
        board_array[x][y] = 3
        snake_array.append([x,y])
        del_x, del_y = snake_array.popleft() ## 뱀의 전체 길이는 변하지 않아야 하기 때문에 꼬리를 제거
        board_array[del_x][del_y] = 0
        time = time + 1
    ## 나머지는 이동한 위치가 벽(=1)이거나 자신의 몸(=3)이므로 stop
    else:
        time = time + 1
        break
    ## 뱀의 방향 전환 정보
    if len(L_array) != 0:
        if L_array[0][0] == time:
            if L_array[0][1] == 'L': ## 왼쪽으로 90도 회전
                d = (d-1)%4
            elif L_array[0][1] =='D': ## 오른쪽으로 90도 회전
                d = (d+1)%4
            del L_array[0] ## 방향 전환했으므로 제거
In [6]:
print(time)
9