[백준(BOJ)] 3190번 : 뱀 - PYTHON[파이썬]

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

3190번: 뱀

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

 

---

 

⊙ 문제 접근 과정

 

뱀의 머리와 꼬리를 알기 위해서 큐를 사용한다.

 

아래에 왜 큐를 사용해야 하는지 설명하겠다.

 

만약 다음 칸에 사과가 있다면 뱀의 길이는 증가한다.

사과가 존재하지 않으면 뱀의 길이는 유지된다.

 

그렇다는 말은 사과가 존재하면 뱀의 꼬리는 움직이지 않고,

사과가 존재하지 않으면 꼬리는 움직여야 한다.

 

꼬리가 움직여야 하는 좌표를 알아야 하기에 큐를 사용한다.

 

해당 움직임을 한번씩 할 때마다 count up을 해주면 된다.

범위를 벗어나거나 자신의 몸을 만나면 게임은 종료된다.

 

 

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
arr = [[0] * N for _ in range(N)]
direction = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}
q = deque()
time = deque()

K = int(input())
for i in range(K):
    x, y = map(int, input().split())
    arr[x-1][y-1] = 1

L = int(input())
for i in range(L):
    X, C = input().split()
    time.append([int(X), C])


def Dummy():
    d = 0
    count = 0
    nx, ny = 0, 0
    q.append((nx, ny))
    arr[nx][ny] = 4
    while True:
        count += 1
        nx = nx + direction[d][0]
        ny = ny + direction[d][1]

        if not 0 <= nx < N or not 0 <= ny < N:
            break

        if arr[nx][ny] == 1:
            arr[nx][ny] = 4
            q.append((nx, ny))

        elif arr[nx][ny] == 0:
            arr[nx][ny] = 4
            q.append((nx, ny))
            delX, delY = q.popleft()
            arr[delX][delY] = 0

        elif arr[nx][ny] == 4:
            break

        if len(time) and time[0][0] == count:
            t, nd = time.popleft()
            if nd == 'L':
                d = (d + 3) % 4
            elif nd == 'D':
                d = (d + 1) % 4

    return count


print(Dummy())

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!