[알고리즘][Python] 백준(BOJ) 3190 뱀_파이썬

 

3190 뱀    www.acmicpc.net/problem/3190

3190번: 뱀

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 구현, 자료 구조, 시뮬레이션, 덱, 큐

 

 

 

 

 

 

 

풀이

<내용>

• n X n 크기의 maps를 0으로 초기화한다.
• 사과가 있는 곳을 1로 표시한다.
• 현재 방향에 따라, D, L에 따라서 움직임을 다르게 하기
• 사과를 먹었을 때는 꼬리가 늘어난 채 유지
• 사과를 먹지 못했을 때, 꼬리를 줄이고 몸의 길이는 그래도
• 꼬리 정보를 가지고 있는 deque를 만든다.
• 자신의 몸과 부딪히거나 벽과 부딪히면 게임을 끝낸다.

 

 

<코드>

from collections import deque
import sys
input = sys.stdin.readline

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

n = int(input())
k = int(input())
maps = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(k):
    row, col = map(int, input().rstrip().split())
    maps[row-1][col-1] = 1
l = int(input())
direction = []
for _ in range(l):
    x, c = input().rstrip().split()
    direction.append((int(x), c))
    
x, c = direction[0]
tail = deque()
tail.append((0, 0))
i, j = 0, 0
maps[i][j] = -1
idx = 1
time = 0
d = 0
while True:
    if time == x:
        if c == 'D':
            d -= 1
            if d == -1:
                d = 3
        else:
            d += 1
            if d == 4:
                d = 0
        if idx < l:
            x, c = direction[idx]
            idx += 1
        
    new_i, new_j = i+dx[d], j+dy[d]
    time += 1
    if 0 <= new_i < n and 0 <= new_j < n:
        if maps[new_i][new_j] == -1:
            print(time)
            break
        elif maps[new_i][new_j] == 0:
            maps[new_i][new_j] = -1
            tail.append((new_i, new_j))
            p, q = tail.popleft()
            maps[p][q] = 0
        else:
            maps[new_i][new_j] = -1
            tail.append((new_i, new_j))
        i, j = new_i, new_j
    else:
        print(time)
        break