파이썬 백준 알고리즘 해설: 뱀 게임 3190

안녕하세요! 이번에는 파이썬을 이용하여 백준 알고리즘 문제 중 하나인 "뱀 게임"을 해결해 보겠습니다. 뱀 게임은 주어진 조건에 따라 뱀을 움직이고, 게임이 종료될 때까지 생존 시간을 구하는 문제입니다. 이제부터 문제의 내용과 해결 방법에 대해 자세히 알아보도록 하겠습니다.

 

바로 아래 정보에서 공부해봅시다!

백준 알고리즘 로고

문제 내용

주어진 N x N 크기의 격자에서 뱀 게임을 진행합니다. 뱀은 초기에 (0, 0) 위치에서 시작하며, 오른쪽을 향해 움직입니다. 뱀은 상하좌우로 이동할 수 있으며, 이동 방향은 시계 방향으로 돌아갈 수도 있습니다. 격자 내에는 뱀, 사과, 그리고 빈 공간이 있습니다. 뱀이 사과를 먹으면 길이가 1 증가하며, 뱀의 머리부분이 이동한 위치에 사과가 있으면 사과가 없어집니다.

게임은 다음과 같은 조건으로 진행됩니다.

• 게임 시작 시간은 0이고, 1초마다 1초씩 증가합니다.
• 뱀은 매 초마다 이동 방향에 따라 한 칸씩 이동합니다.
• 만약 이동한 위치에 벽이나 자기 자신의 몸이 있으면 게임이 종료됩니다.
• 게임이 종료되었을 때의 생존 시간을 구해야 합니다.

위의 문제 내용을 기반으로 주어진 코드를 분석하고, 문제를 해결하는 방법에 대해 알아보겠습니다.

문제 이해하기

주어진 코드는 뱀 게임을 구현한 파이썬 코드입니다. 코드를 통해 게임의 진행 방식과 조건들을 확인할 수 있습니다. 먼저, 필요한 변수와 상수를 초기화한 후, 뱀을 이동시키는 함수인 **move()**를 구현하고 있습니다. move() 함수는 뱀을 이동시키면서 게임이 종료될 때까지의 시간을 반환합니다.

코드를 분석하면서 자세한 내용을 확인해보겠습니다.

풀이 코드

pythonCopy code
import sys
from collections import deque

input = lambda: sys.stdin.readline()

EMPTY, SNAKE, APPLE = 0, 1, 2
LEFT, RIGHT = 'L', 'D'

# 오른쪽, 아래, 왼쪽, 위 (시계 방향)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def rotate(time, direction):
    if time not in rotations:
        return direction

    if rotations[time] == RIGHT:
        return (direction + 1) % 4

    if rotations[time] == LEFT:
        return 3 if not direction else direction - 1

def move():
    time, direction = 0, 0

    head_x, head_y = 0, 0
    snakes = deque([(head_x, head_y)])

    while True:
        direction = rotate(time, direction)
        nx = head_x + dx[direction]
        ny = head_y + dy[direction]

        time += 1

        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            break

        if matrix[nx][ny] == SNAKE:
            break

        if matrix[nx][ny] != APPLE:
            tail_x, tail_y = snakes.popleft()
            matrix[tail_x][tail_y] = EMPTY

        matrix[nx][ny] = SNAKE
        snakes.append((nx, ny))
        head_x, head_y = nx, ny

    return time

n = int(input())

rotations = {}
matrix = [[EMPTY] * n for _ in range(n)]

for _ in range(int(input())):
    row, col = map(int, input().split())
    matrix[row - 1][col - 1] = APPLE

for _ in range(int(input())):
    second, rotation = input().split()
    rotations[int(second)] = rotation

print(move())

풀이 방법

주어진 코드에서 move() 함수가 뱀을 이동시키는 로직을 담당합니다. 이제 move() 함수를 자세히 분석해보겠습니다.

1. 초기화 단계
   • **time**과 **direction**을 초기화합니다.
   • 뱀의 시작 위치인 (0, 0)을 head_x, **head_y**로 초기화합니다.
   • **snakes**라는 데크(deque)에 뱀의 머리 위치를 추가합니다.
2. 뱀 이동
   • 계속해서 반복되는 while 루프를 통해 뱀을 이동시킵니다.
   • direction 변수를 현재 시간에 맞춰 회전시킵니다. rotate() 함수를 호출하여 시간에 따른 회전 방향을 결정합니다.
   • **nx**와 **ny**를 이용해 다음 이동할 위치를 계산합니다.
   • **time**을 1 증가시킵니다.
   • 다음 이동할 위치가 격자를 벗어나거나, 뱀의 몸통과 충돌한 경우, 게임이 종료됩니다.
   • 다음 이동할 위치에 사과가 없는 경우, 뱀의 꼬리 부분을 제거합니다.
   • 다음 이동할 위치에 뱀을 추가하고, **head_x**와 **head_y**를 갱신합니다.
3. 결과 반환
   • **time**을 반환하여 게임이 종료될 때까지의 생존 시간을 출력합니다.

이제 코드를 통해 뱀 게임을 해결할 수 있게 되었습니다!

시간 복잡도

해당 알고리즘의 시간 복잡도는 O(n^2)입니다. 이는 주어진 N x N 크기의 격자에서 모든 칸을 방문해야 하기 때문입니다.

이상으로 파이썬을 이용한 백준 알고리즘 "뱀 게임" 해설을 마치도록 하겠습니다. 코드를 통해 문제를 해결하고, 시간 복잡도를 분석해 보았습니다. 다른 문제에 대한 해설이 필요하신 경우 언제든지 말씀해주세요. 감사합니다!

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음