[Python] 3190 뱀

1. 문제 📚

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

2. 입출력 예 📋

3. 알고리즘 ✅

처음에 문제를 이해하는 데만 오래걸렸다;; 

초기 시작을 (0, 0)으로 두고 1초라고 둬야한다

보기 쉽게 $을 뱀 @ 을 사과라고 뒀다

 

예제1을 출력해보면 

time:  1 direction:  Right
$ . . . . .
. . . . @ .
. . . @ . .
. . . . . .
. . @ . . .
. . . . . .
time:  2 direction:  Right
. $ . . . .
. . . . @ .
. . . @ . .
. . . . . .
. . @ . . .
. . . . . .
time:  3 direction:  Right
. . $ . . .
. . . . @ .
. . . @ . .
. . . . . .
. . @ . . .
. . . . . .
time:  4 direction:  Down
. . . $ . .
. . . . @ .
. . . @ . .
. . . . . .
. . @ . . .
. . . . . .
time:  5 direction:  Down
. . . . . .
. . . $ @ .
. . . @ . .
. . . . . .
. . @ . . .
. . . . . .
time:  6 direction:  Down
. . . . . .
. . . $ @ .
. . . $ . .
. . . . . .
. . @ . . .
. . . . . .
time:  7 direction:  Down
. . . . . .
. . . . @ .
. . . $ . .
. . . $ . .
. . @ . . .
. . . . . .
time:  8 direction:  Down
. . . . . .
. . . . @ .
. . . . . .
. . . $ . .
. . @ $ . .
. . . . . .
time:  9 direction:  Down
. . . . . .
. . . . @ .
. . . . . .
. . . . . .
. . @ $ . .
. . . $ . .

뱀의 머리나 몸이 벽에 닿는 순간 멈춰야한다 

 

3가지의 조건을 따라

1. 사과를 먹으면 뱀의 길이가 늘어나야하기 때문에 뱀의 길이를 queue라고 생각하고

2. 사과가 없으면 다음칸으로 전진하고 꼬리를 원래의 값으로 돌려주기

3. 그 이외의 값(뱀의 몸이 닿는 순간) 멈추기

 

또한 방향설정이 조건에 있기 때문에 L, D 조건에 따라 방향을 바꿔줘야한다

4. 소스코드 💻

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

N = int(input().strip())
K = int(input().strip())

board = [[0 for _ in range(N)] for _ in range(N)]

queue = deque([])
queue.append([0, 0])

# 사과
for i in range(K):
    x, y = map(int, input().strip().split())
    board[x - 1][y - 1] = 2

changeDir = defaultdict(str)
L = int(input().strip())

for i in range(L):
    x, c = input().strip().split()
    changeDir[int(x)] = c

x, y = 0, 0
# 뱀 초기 상태
board[x][y] = 1
time = 0
direction = 0

# 현재방향
now = 'Right'

def go(dir):
    global time
    global changeDir
    global now

    if time in changeDir:
        if dir == 'Right':
            if changeDir[time] == 'L':
                nx, ny = x - 1, y
                now = 'Up'
            elif changeDir[time] == 'D':
                nx, ny = x + 1, y
                now = 'Down'
        elif dir == 'Down':
            if changeDir[time] == 'L':
                nx, ny = x, y + 1
                now = 'Right'
            elif changeDir[time] == 'D':
                nx, ny = x, y - 1
                now = 'Left'
        elif dir == 'Left':
            if changeDir[time] == 'L':
                nx, ny = x + 1, y
                now = 'Down'
            elif changeDir[time] == 'D':
                nx, ny = x - 1, y
                now = 'Up'
        elif dir == 'Up':
            if changeDir[time] == 'L':
                nx, ny = x, y - 1 # 수정
                now = 'Left'
            elif changeDir[time] == 'D':
                nx, ny = x, y + 1
                now = 'Right'
    else:
        if dir == 'Right':
            nx, ny = x, y + 1
        elif dir == 'Down':
            nx, ny = x + 1, y
        elif dir == 'Left':
            nx, ny = x, y - 1
        elif dir == 'Up':
            nx, ny = x - 1, y

    return nx, ny

while True:
    x, y = go(now)
    time += 1

    if x < 0 or x >= N or y < 0 or y >= N:
        break

    # 사과 존재
    if board[x][y] == 2:
        # 사과 먹음처리
        board[x][y] = 1
        queue.append([x, y])
    # 전진
    elif board[x][y] == 0:
        # 뱀 이동
        board[x][y] = 1
        queue.append([x, y])

        # 뱀 꼬리 가져오기
        px, py = queue.popleft()
        board[px][py] = 0
    # 뱀이 자기 몸에 닿는 순간
    else:
        break

print(time)

다른 사람들 코드보니 방향 분기를 아래와 같이 더 간편하게 짰다 ^^ ; ;

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(alpha):
    global direction
    if alpha == 'L':
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
        
while True:
    cnt += 1
    x += dx[direction]
    y += dy[direction]
    """
    이하생략
    """

방향 조건이 조금 헷갈려서 6시간 동안 삽질했다 

 

예를들어 나는 계속 오른쪽 방향 + L (왼쪽)  = 아래쪽이라고 생각했다 ;;

방향이 왼쪽으로 가도록 돌리니까 아래쪽나오길래 계속 그렇게 로직을 짜서 답이 안나왔었다

오른쪽방향 + L (왼쪽) = 위쪽 방향이다.

L(반시계방향), D(시계방향)으로 생각해야됐었다

 

앞으로는 조건을 더 신경써야겠다 〰️