[백준-골드5] 3190번 뱀 (구현, 덱, 큐, 파이썬)

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

3190번: 뱀

 

<내 코드>

- 사과의 좌표를 입력 받을 때 문제는 가장 좌측 상단이 (1,1)이므로 인덱스 처리 주의

- 또한 해당 시간에 회전 방향을 입력받을 때는 딕셔너리로 입력 받았다. (구현 용이)

- 이동 방향(dx,dy)은 북,동(오른쪽),남,서 순서로 설정하였기 때문에 초기에 뱀은 오른쪽을 향해서 d = 1로 설정 

- 뱀의 위치와 크기를 deque에 넣어서 체크했다. 시작점은 가장 좌측 상단이기때문에 (0,0)을 넣어줌.

- turn 함수는 회전 방향('L' or 'D')를 입력으로해서 방향을 변경해주고 d를 리턴한다.(하단 그림 참고)

 

- while문을 통해 종료조건이 될 때 까지 동작을 반복한다.

  - 시간을 계속 증가시키고, 이동 방향으로 한칸씩 움직인다.

  - 이 때 이동 명령에 주어진 시간이 되면 방향을 회전시킨다.

  - nx, ny가 보드 범위를 벗어나지 않는 경우

    - 만약 snake에 [nx,ny]가 이미 있으면 뱀의 몸끼리 부딪힌 경우라 종료처리한다.

    - 다음 위치에 사과가 있으면 사과를 먹고, snake에 좌표를 추가해 이동하며 길이를 늘린다.

    - 다음 위치에 사과가 없으면 snake에 좌표를 추가해 이동하고, popleft를 통해 꼬리를 줄여서 길이를 유지한다.

  - 범위를 범어난 경우는 종료 처리한다.

 

from collections import deque
import sys
## 입력 ##
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
board = [[0]*n for _ in range(n)]
for _ in range(k):
    x,y = map(int, sys.stdin.readline().split())
    board[x-1][y-1] = 1 #사과 위치 표시
    
info = {} #방향 전환 정보 저장 딕셔너리, 키:시간, 밸류:방향
L = int(input())
for _ in range(L):
    x,c = sys.stdin.readline().split()
    info[int(x)] = c

# 이동 방향, 북,동(우),남,서 순서 
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

snake = deque()
snake.append([0,0]) #시작 위치 넣어줌
time = 0 #게임 시간
d = 1 #처음엔 오른쪽을 향함
nx, ny = 0, 0

def turn(direction):
    global d
    if direction == 'L': #왼쪽 회전
        d = d-1
        if d == -1: #북->서 로 회전할때
            d = 3
    else: #오른쪽 회전
        d = d +1
        if d == 4: # 서->북 회전
            d = 0
    return d

while True:
    time+=1
    nx = nx + dx[d]
    ny = ny + dy[d]
    
    #방향 전환
    if time in info.keys():
        d = turn(info[time])
        
    if 0<=nx<n and 0<=ny<n: #범위 체크
        #몸에 부딪힌 경우
        if [nx,ny] in snake:
            break
            
        #다음 위치에 사과가 있으면 길이 증가
        if board[nx][ny] == 1:
            board[nx][ny] = 0 #사과먹음
            snake.append([nx,ny])
            
        #다음 위치에 사과가 없는 경우
        elif board[nx][ny] ==0:
            snake.append([nx,ny])
            snake.popleft() #꼬리 줄여서 길이 유지
            
    else: #범위 범어난 경우
        break
    
print(time)

 

turn함수 동작 원리