[Python/백준] 3190_뱀

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

3190번: 뱀

<문제 해설>

구현 시뮬레이션 + queue를 사용하는 문제이다. 

뱀이 현제 어디 있는지 2차원 배열에 기록해서 뱀이 몸통에 충돌하는지 계산하고 뱀의 머리부터 몸통, 꼬리의 위치를 기록해서 시간이 지날때마다 뱀이 이동하도록 해야한다.

2차원 배열에 뱀은 1로 사과는 2로 저장한다.

뱀의 머리와 꼬리는 배열로 저장하는데 이때 머리부터 꼬리의 값을 계속 변경해주면 시간이 너무 걸리니 새로 이동하는 좌표를 배열의 머리로 넣어주고 배열의 꼬리가 이동할땐 배열의 꼬리를 삭제하는 방식으로 진행한다.

뱀의 좌표는 snail이라는 deque배열에 저장하고

board에 뱀의 위치를 기록한다.

뱀의 머리의 방향또한 기록해야 하기때문에 move에 뱀이 보는 방향을 저장하고 direction변수로 방향을 관리한다.

move =[[0,1],[1,0],[0,-1],[-1,0]]

              동      남      서     북

이런 방식으로 설정한다.
command배열의 초가 됐다면 direction을 C를 받아서 변경해준다. D는 왼쪽으로 90도 회전임으로 (만약 동이면 남으로) (direction + 1)%4 D는 오른쪽으로(만약 동이면 북으로) (direction + 1)%4를 해준다.

1. 초를 증가시키고 뱀의 머리가 이동할 좌표를 계산한다.
   이때 뱀의 머리가 뱀의 몸통에 닿거나 board를 빠저나가면 기록해둔 초를 출력하고 함수를 정지한다.
2. 뱀저장 배열의 끝에 뱀의 이동할 곳의 좌표를 넣어준다. 이러면 뱀의 머리가 이좌표에 있다는 것이 된다.
   이때 만약 뱀의 머리가 있는 board의 좌표에 사과가 없는 경우 뱀 배열의 왼쪽 끝의 값을 빼서 꼬리또한 이동한것처럼 
   만들고 board의 원래 꼬리 좌표또한 0으로 만들어 꼬리가 이동했음을 기록한다.
   사과가 있으면 뱀의 꼬리는 이동하지 않는것처럼 보이니 이때 이후의 과정을 수행하지 않는다.
3. 만약 command배열에 초가 현제 초라면 direction을 계산해준다.
4. 1번으로 돌아간다.

<예시>

1번 예시는 다음과 같이 진행된다.

[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 2, 0]
[0, 0, 0, 2, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 2, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 2, 1, 0, 0]
[0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 2, 1, 0, 0]
[0, 0, 0, 1, 0, 0]

3번 예시는 다음과 같이 진행된다.

[1, 2, 2, 0, 2, 2, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[1, 1, 2, 0, 2, 2, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[1, 1, 1, 0, 2, 2, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 1, 1, 1, 2, 2, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 1, 1, 1, 1, 2, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 1, 1, 1, 1, 1, 2, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 1, 1, 1, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 0, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 0, 0, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 0, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

[0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

<코드>

def game():
    global second, direction
    second += 1
    for n in range(N):
        print(board[n])
    print('')
    mx = snail[-1][1] + move[direction][1]
    my = snail[-1][0] + move[direction][0]
    if N > my > -1 and N > mx > -1 and board[my][mx] != 1:
        snail.append([my,mx])
        if board[my][mx] != 2:
            yx = snail.popleft()
            board[yx[0]][yx[1]] = 0
        board[my][mx] = 1
        if len(command) != 0 and command[0][0] == second:
            if command[0][1] == 'D':
                direction = (direction + 1)%4
            else:
                direction = (direction - 1)%4
            command.popleft()
        game()
    else:
        print(second)
        return

import sys
from collections import deque
sys.setrecursionlimit(10**7)
N = int(sys.stdin.readline())
K = int(sys.stdin.readline())

snail = deque([[0,0]])
board = []
command = deque([])
for n in range(N):
    board.append([0]*N)

for k in range(K):
    y,x  = map(int,sys.stdin.readline().split())
    board[y-1][x-1] = 2
board[0][0] = 1
L = int(input())

move = [[0,1],[1,0],[0,-1],[-1,0]]

for l in range(L):
    X, com = sys.stdin.readline().split()
    command.append([int(X),com])

second = 0
direction = 0
game()

<코드 설명>

def game():
    global second, direction //초, 방향은 전역변수로 만들어서 언제나 쓸수 있게 한다.
    second += 1 //초를 증가시킨다.
    mx = snail[-1][1] + move[direction][1] //머리가 이동할 좌표를 mx,my에 저장한다.
    my = snail[-1][0] + move[direction][0]
    if N > my > -1 and N > mx > -1 and board[my][mx] != 1: //뱀이 밖에 나갔거나 몸통에 충동하지 않는다면
        snail.append([my,mx]) //뱀에 머리에 이동할 좌표를 넣어준다.
        if board[my][mx] != 2: //사과에 머리가 도착하지 않았다면
            yx = snail.popleft() //꼬리를 제거
            board[yx[0]][yx[1]] = 0 //꼬리좌표의 1도 0으로 변경
        board[my][mx] = 1 //새로운 머리의 좌표를 1로 변경
        if len(command) != 0 and command[0][0] == second: //명령이있는 초라면
            if command[0][1] == 'D': //방향값에 따라 방향 변경
                direction = (direction + 1)%4 
            else:
                direction = (direction - 1)%4
            command.popleft() //command 삭제
        game() //배열 반복
    else:
        print(second) //초 출력
        return

import sys 
from collections import deque
sys.setrecursionlimit(10**7) //recursive에러가 나기때문 적어줬다
N = int(sys.stdin.readline()) //값 받기
K = int(sys.stdin.readline())

snail = deque([[0,0]])
board = []
command = deque([])
for n in range(N): //board배열 형성
    board.append([0]*N)

for k in range(K): //사과를 배열에 저장
    y,x  = map(int,sys.stdin.readline().split())
    board[y-1][x-1] = 2
board[0][0] = 1
L = int(input())

move = [[0,1],[1,0],[0,-1],[-1,0]] //뱀의 방향 배열

for l in range(L): //command를 저장
    X, com = sys.stdin.readline().split()
    command.append([int(X),com])

second = 0
direction = 0
game()