[Python] 백준 3190 : 뱀 (implementation)

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

머리말

아, 뱀 게임 로직 짜는 거구나,, 재밌겠다,,
처음에는 뱀의 위치 정보를 어떻게 구현해야 할지 고민을 하다가 큐가 문득 떠올랐다.
자료구조 때 배운 것을 바로 적용할 수 있는 능력을 키우자!

 

접근 방법

차근차근 해결하면 된다.

• 맵 정보를 저장하는 graph 리스트에 사과 위치를 2로 저장하였다.
• dx, dy 방향 전환을 동, 북, 서, 남 형식으로 저장하여 방향에 맞게 circle로 돌 수 있도록 하였다.
• cnt는 게임의 시간 정보를 나타내는 변수로, 이것을 logs 배열에 존재하는지 확인 후 방향 전환을 고려하였다.
• 뱀의 위치 정보를 저장하는 snake 리스트를 큐(deque)를 사용하여 이동할 때 머리는 push, 꼬리는 popleft 하였다.

 

코드

from collections import deque

n=int(input())
k=int(input())
graph=[[0] * n for _ in range(n)]
for _ in range(k):
    a,b=map(int,input().split())
    graph[a-1][b-1] = 2 #사과 위치
l=int(input())
logs=[]
for _ in range(l):
    a,b=input().split()
    logs.append([int(a),b])

dx = [0, -1, 0, 1] #동북서남
dy = [1, 0, -1, 0]

def solution():
    cnt = 0
    logIdx = 0
    x, y = 0, 0
    dir = 0
    graph[0][0] = 1
    snake=deque([(0,0)])
    while True:
        cnt += 1
        nx = x + dx[dir]
        ny = y + dy[dir]

        if logIdx < len(logs) and cnt == logs[logIdx][0]:
            if logs[logIdx][1] == 'L':
                dir = (dir + 1) % 4
            else:
                dir = (dir - 1) % 4
            logIdx += 1

        if 0 > nx or nx >= n or 0 > ny or ny >= n: #벽에 부딪힐 때
            return cnt
        elif graph[nx][ny] == 1: #자기자신의 몸과 부딪힐 때
            return cnt
        elif graph[nx][ny] == 2: #사과 만날 때
            graph[nx][ny] = 1
            snake.append((nx,ny))
        else:
            graph[nx][ny] = 1
            snake.append((nx,ny))
            graph[snake[0][0]][snake[0][1]] = 0
            snake.popleft()

        x, y = nx, ny

print(solution())