[python] 백준 - 3190. 뱀 (삼성 SW 역량 테스트 기출 문제)

🤔문제 해결

• G5 | deque, 시뮬레이션

1. deque 를 이용하여 뱀을 만든다. deque의 앞쪽은 꼬리, deque의 뒷쪽은 머리 (반대로 해도 상관없음)
2. 머리를 방향에 따라 한칸 늘린다.(deque에 머리 추가: append())
   1. 벽에 부딪히지 않고, 뱀의 몸통에 부딪히지 않으면 통과
      1. 이 때 머리의 위치에 사과가 있으면 통과
      2. 없으면 꼬리를 줄인다.( deque에서 꼬리를 제거: popleft())
3. 매초 세주면서 해당 초에 오더가 있으면 ( 방향 바꾸기 ) 진행 방향을 바꿔준다.

주의: 사과를 먹으면 맵에서 사과 지우기

 

 

💻소스 코드

from sys import stdin
from collections import deque

input = stdin.readline


def move_snake(direc, location):
    # 머리 늘릴 곳 정하기
    cx, cy = location
    nx, ny = 0, 0
    if direc == 'R':
        nx, ny = cx, cy + 1
    elif direc == 'L':
        nx, ny = cx, cy - 1
    elif direc == 'D':
        nx, ny = cx + 1, cy
    elif direc == 'U':
        nx, ny = cx - 1, cy

    # 벽이나 뱀의 몸통에 부딪히지 않을 때
    if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] != 1:
        # 머리 늘리기
        snake.append((nx, ny))

        if maps[nx][ny] != 4:  # 사과가 아니면 꼬리 땡기기
            tx, ty = snake.popleft()
            maps[tx][ty] = 0

        # 맵에 뱀 놓기
        maps[nx][ny] = 1
    else:
        return False
    return True


def change_direction(c_direction, r_direction):
    # 현재방향, 회전방향
    if r_direction == 'L':
        if c_direction == 'R':
            c_direction = 'U'
        elif c_direction == 'L':
            c_direction = 'D'
        elif c_direction == 'D':
            c_direction = 'R'
        elif c_direction == 'U':
            c_direction = 'L'
    if r_direction == 'D':
        if c_direction == 'R':
            c_direction = 'D'
        elif c_direction == 'L':
            c_direction = 'U'
        elif c_direction == 'D':
            c_direction = 'L'
        elif c_direction == 'U':
            c_direction = 'R'
    return c_direction


if __name__ == '__main__':
    N = int(input())  # 판의 크기
    K = int(input())  # 사과의 개수

    # 맵과 사과의 위치와 뱀의 위치 # 사과는 4 뱀은 1
    maps = [[0] * N for _ in range(N)]
    for _ in range(K):
        x, y = map(int, input().split())
        maps[x - 1][y - 1] = 4
    maps[0][0] = 1

    # 오더
    L = int(input())  # 방향 전환 횟수
    order = [0] * 10000
    for _ in range(L):
        x, c = input().split()  # x: 초, c: 방향 (L 왼쪽,  D 오른쪽) 으로 90도 회전
        order[int(x)] = c

    # 뱀
    snake = deque([(0, 0)])  # 앞쪽 인덱스가 뱀 꼬리, 뒤쪽 인덱스가 뱀 머리
    direction = 'R'  # 방향 R, L, D, U
    second = 0
    while True:
        second += 1
        # 이동하기
        if move_snake(direction, snake[-1]) is False:
            break

        # 정해진 시간초대에 방향 바꾸기
        if order[second]:
            direction = change_direction(direction, order[second])

    print(second)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

3190번: 뱀