[백준] 3190번 뱀 파이썬 풀이

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

3190번: 뱀

---

1. 풀이

• N x N 크기의 2차원 리스트를 생성하고, (i, j) 좌표에 빈 칸, 뱀 존재, 사과 존재 여부를 저장하자

필자는 maps라는 N x N 2차원 리스트를 생성하고 빈 칸은 0, 뱀이 있으면 1, 사과가 있으면 2로 표현했다. 따라서 board[i][j]로 접근하면 곧바로 해당 칸의 정보를 알아낼 수 있다.

이때 리스트는 인덱스 (0, 0)부터 시작하는데, 문제에서는 (1, 1)부터 시작한다고 한다. 따라서 인덱싱하기 쉽도록, 입력 좌표에 -1하여 (0, 0) 기준의 좌표로 조정했다.

 

 

• 뱀의 몸통이 존재하는 모든 칸을 deque에 담아놓자

이미 maps 리스트를 통해 maps[i][j] == 1인 경우, 그곳이 뱀의 몸통이란 걸 알 수 있다. 그러나 자기 자신의 몸과 부딪혔는지 여부를 확인하기 위한 용도로 사용된다.

deque 자료구조를 따로 사용하는 이유는 이동한 칸에 사과가 없을 경우, 꼬리를 한 칸 비워야 하기 때문이다. 새로 이동한 칸을 append()하고, 꼬리는 popleft()를 통해 제거하면 된다. 당연히 그 꼬리 좌표의 값은 1에서 0으로 바꾸어 주어야 한다.

 

 

• 방향이 바뀌는 타이밍에 유의하자

3초에 오른쪽으로 90도 회전한다고 하면, 1초 만들고 이동 → 2초 만들고 이동 → 3초 만들고 이동, 그 이후에 회전이다. 처음에 1초 이동 → 2초 이동 → 3초 회전 후 이동으로 잘못 생각하여 잠시 헤맸다.

 

 

 

2. 정답 코드

from collections import deque
import sys

input = sys.stdin.readline


def validate_coordinate(x, y):
    return False if x < 0 or x >= N or y < 0 or y >= N else True


def check_time_and_change_direction(time, d):
    if info and time == int(info[0][0]):
        if info[0][1] == 'L':
            d += 1
        else:
            d -= 1
        info.popleft()
    return d % 4


def start(x, y, d):
    time = 0
    snake = deque([(0, 0)])
    maps[0][0] = 1

    while True:
        time += 1
        dx, dy = x + directions[d][0], y + directions[d][1]

        if not validate_coordinate(dx, dy) or maps[dx][dy] == 1:
            return time  # face to wall or itself

        snake.append((dx, dy))

        if maps[dx][dy] == 0:  # no apple
            tail_x, tail_y = snake.popleft()
            maps[tail_x][tail_y] = 0

        maps[dx][dy] = 1
        x, y = dx, dy
        d = check_time_and_change_direction(time, d)


# main
N = int(input())
maps = [[0] * N for _ in range(N)]  # 0: empty, 1: snake, 2: apple
K = int(input())
for _ in range(K):
    r, c = map(lambda x: int(x) - 1, input().split())  # change standard: (1, 1) -> (0, 0)
    maps[r][c] = 2
L = int(input())
info = deque([tuple(input().rstrip().split()) for _ in range(L)])
directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]  # right, up, left, down

print(start(0, 0, 0))