(Python) 백준 3190

백준 3190

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	61241	25493	17032	39.912%

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

---

답안

from collections import deque
import sys

class Snake:
    time_elapsed = 0
    x = 0
    y = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dir = 0
    body = deque([(0, 0)])
    board = None

    def move_to(self, next_move):
        time, rotate_dir = next_move
        for _ in range(time - self.time_elapsed):
            self.forward()

            if self.collided() or not self.board.is_inside(self.x, self.y):
                print(self.time_elapsed)
                exit()

            self.stretch()
            if not self.eat_apple():
                self.shrink()

        self.rotate(rotate_dir)

    def forward(self):
        self.x += self.dx[self.dir]
        self.y += self.dy[self.dir]
        self.time_elapsed += 1

    def collided(self):
        return (self.x, self.y) in self.body

    def stretch(self):
        self.body.append(tuple([self.x, self.y]))

    def eat_apple(self):
        if self.board.apple_exist[self.x][self.y]:
            self.board.apple_exist[self.x][self.y] = False
            return True
        else:
            return False

    def shrink(self):
        self.body.popleft()

    def rotate(self, rotate_dir):
        match rotate_dir:
            case 'D':
                self.dir = (self.dir + 1) % 4
            case 'L':
                self.dir = (self.dir + 3) % 4

class Board:
    def __init__(self, board_size, apples):
        self.size = board_size
        self.apple_exist = [([False] * board_size) for _ in range(board_size)]
        for apple in apples:
            x, y = apple
            self.apple_exist[x][y] = True

    def is_inside(self, x, y):
        return 0 <= x < self.size and 0 <= y < self.size

input = sys.stdin.readline
board_size = int(input())
num_apple = int(input())

apples = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(num_apple)]

num_move = int(input())
moves = []
for _ in range(num_move):
    time, rotation_dir = input().split()
    moves.append(tuple([int(time), rotation_dir]))
moves.append(tuple([10101, 'D']))
moves.reverse()

snake = Snake()
snake.board = Board(board_size, apples)

while moves:
    snake.move_to(moves.pop())
print(snake.time_elapsed)

풀이

어려운 알고리즘 기법을 써야 하는 것도, 구현이 여러가지 예외 때문에 복잡한 것도 아니었지만, 신경써야 할 것들이 다소 있었던 문제였다.

input = sys.stdin.readline
board_size = int(input())
num_apple = int(input())

apples = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(num_apple)]

num_move = int(input())
moves = []
for _ in range(num_move):
    time, rotation_dir = input().split()
    moves.append(tuple([int(time), rotation_dir]))
moves.append(tuple([10101, 'D']))
moves.reverse()

snake = Snake()
snake.board = Board(board_size, apples)

위 코드는 입력을 받아준 뒤, 필요한 객체를 초기화하는 부분이다.

문제에서 주어진 보드의 크기 N(board_size), 사과의 개수 K(num_apple), 사과의 위치(apples), 뱀의 방향 전환 횟수(num_move), 뱀의 방향 전환 배열(moves)를 차례로 받아주었다.

사과의 위치(apples)는 (x, y) 튜플로 이뤄진 리스트이다. apples는 index를 1, 2, 3과 같이 1에서 시작하도록 하지 않고, 0, 1, 2와 같이 0부터 시작하도록 하였다. (lambda x: int(x)-1, …)

뱀의 방향 전환 배열(moves)는 (방향 전환 시각, 회전 방향) 튜플로 이뤄진 리스트이다. moves 배열을 뒤집어(moves.reverse()), 이후 moves 배열에서 하나씩 방향 전환 정보를 빼서 처리했을 때 성능 하락이 없도록 하였다.

moves.append(tuple([10101, 'D'])) 부분에서 10101이라는 숫자를 넣은 이유는, 전환 배열이 모두 빈 이후에도 뱀이 이동을 해야 하기 때문이다. 문제에서 방향 X는 10,000 이하의 양의 정수라는 조건이 있음에도 불구하고 뱀은 10000칸을 넘어 이동할 수 있음에 유의하자. 예를 들어 10000칸 째가 되었을 때 (0, 0) 좌표에서 오른쪽으로 방향 전환을 했을 때 10100칸 이동이 가능하다.

문제를 해결하는 코드를 더 간결하고 이해하기 쉽게 만들기 위해 Snake라는 클래스를 만들어 사용하였다. 이 문제에서 사용되는 Snake의 객체는 하나이다.

Snake 클래스의 객체는 Board를 포함하고 있다. 게임 보드에 대한 정보를 Snake가 알아야 하기 때문이다.

while moves:
    snake.move_to(moves.pop())
print(snake.time_elapsed)

뱀의 방향 전환 배열(moves)에 담긴 방향 전환 정보를 하나씩 꺼내어 snake 객체에 넣어준다. 방향 전환 배열이 빌 때까지, 혹은 Snake.move_to() 에서 문제에서 원하는 결과값이 나올 때까지 프로그램이 실행된다.

class Snake:
    time_elapsed = 0
    x = 0
    y = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dir = 0
    body = deque([(0, 0)])
    board = None

Snake는 문제에서 주어진 뱀의 이동을 처리하기 위해 다음 멤버 변수들을 둔다.

• time_elapsed: 뱀이 출발한 이후로부터 지금까지 걸린 시간, 또는 뱀이 이동한 타일 수를 나타낸다. 만약 뱀이 자신의 몸과 충돌하거나 벽에 충돌하면, 이 값이 문제의 결과값으로 stdout으로 출력된다.
• x, y: N x N 게임보드에서의 뱀의 머리의 좌표이다. (0 ≤ x < N, 0 ≤ y < N)
• dx, dy, dir: 뱀의 머리가 가리키는 방향을 나타낸다. 0 ≤ dir ≤ 3인 dir의 값에 따라, 뱀은 각각 (0, 1), (1, 0), (0, -1), (-1, 0)의 방향을 가질 수 있다. 만약 뱀이 시계 방향으로 회전하면 dir의 값은 커지고, 반시계방향으로 회전하면 dir의 값은 작아진다. dir 값이 정해진 범위를 넘지 않도록 모듈러 연산을 취한다.
• body: 뱀의 몸통을 저장하는 queue이다. 뱀의 머리가 뱀의 몸통과 충돌하였는지 판단하기 위해, 게임보드 중 뱀의 몸통이 지나가고 있는 칸의 좌표를 queue에 기록해놓았다. 만약 뱀이 앞으로 이동하면, 뱀의 머리가 있는 좌표가 body에 enqueue되고, 꼬리가 있던 좌표가 body에서 dequeue된다.
• board: 게임보드에 놓여 있는 사과를 처리하거나, 뱀이 게임보드 밖을 나갔을 때(벽에 부딪혔을 때)의 처리를 위해, 뱀은 게임보드의 상태를 알아야 하므로 뱀의 멤버 변수로 board를 두었다.

def move_to(self, next_move):
    time, rotate_dir = next_move
    for _ in range(time - self.time_elapsed):
        self.forward()

        if self.collided() or not self.board.is_inside(self.x, self.y):
            print(self.time_elapsed)
            exit()

        self.stretch()
        if not self.eat_apple():
            self.shrink()

    self.rotate(rotate_dir)

이 프로그램에서 가장 핵심적인 역할을 담당하는 move_to 함수이다.

parameter next_move에는 방향을 전환하는 시각(time)과 방향 전환 방향 정보(rotate_dir)가 들어있다.

방향 전환 시각(time)에서 현재까지 진행된 시간(self.time_elapsed)를 뺀 delta time 동안 뱀은 한 방향으로 이동한다. 이때 한 칸씩 뱀을 이동시켜 가며 뱀이 충돌하거나 게임보드 밖으로 나갔는지 체크한다.

self.forward()를 통해 뱀의 대가리를 진행 방향으로 한 칸 이동시킨 뒤, 자기 자신과 충돌했는지( self.collided()), 또는 보드 바깥에 나갔는지(not self.board.is_inside(self.x, self.y)) 판단한다.

만약 그렇다면, 지금까지 걸린 시간을 stdout으로 출력한 뒤, 추가적으로 더 해야 할 동작이 없으므로 프로그램을 종료한다.

그렇지 않다면, self.stretch()를 통해 self.body에 뱀의 대가리 부분의 좌표를 넣고, self.shirink()를 통해 self.body에 뱀의 꼬리 부분의 좌표를 뺌으로써 뱀을 이동을 self.body에 반영시킨다. 이 동작은 자기 자신과의 충돌을 탐지한 이후에 실행되어야 한다.

또한 주의해야 할 부분은, 뱀이 사과를 먹을 경우에는 뱀의 길이가 줄어들지 않는다는 것이다. if not self.eat_apple(): self.shrink()와 같이 뱀이 사과를 먹지 않았을 경우에만 뱀의 길이를 줄이도록 한다.

방향을 전환하기 전까지, 위에 적힌 내용들을 반복하다가 self.rotate()를 통해 뱀의 이동 방향을 전환시킨다.

Snake 클래스의 다른 함수들의 구현은 위의 전체 코드를 참고하길 바란다. 함수 구현이 아주 어렵지 않아 쉽게 이해될 것으로 생각한다.

class Board:
    def __init__(self, board_size, apples):
        self.size = board_size
        self.apple_exist = [([False] * board_size) for _ in range(board_size)]
        for apple in apples:
            x, y = apple
            self.apple_exist[x][y] = True

    def is_inside(self, x, y):
        return 0 <= x < self.size and 0 <= y < self.size

Board 클래스에서는 주로 사과에 대해 책임진다. 사과의 좌표((x, y))가 들어있던 배열인 apples 배열로부터, apple_exist라는 배열을 만든다.

이유는, 뱀과 사과들과의 충돌을 탐지하기 위해서는 뱀이 한 칸 움직일 때마다 전체 사과들의 배열(apples)를 탐색해야 하는데, 이럴 경우 처리 시간이 느려지기 때문이다.

뱀은 최악의 경우 10000번 움직이고 이때마다 전체 사과를 탐색해야 하므로, element의 검색이 효율적인 2차원 배열로 사과들의 정보를 저장하였다.

이와 같이 복잡한 구현 요구사항들을 클래스로 나누어 이해하기 편리하도록 구현하여 보았는데, 문제가 이해되지 않거나, 어떠한 예외 케이스 때문에 문제가 풀리지 않는다면 아래에서 도움을 받을 수 있으니 참고해보자.

• 풀면서 주의할 점

https://www.acmicpc.net/board/view/109911

• 반례 모음

https://www.acmicpc.net/board/view/56469