백준, 뱀

백준, 뱀

 

❓문제

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

3190번: 뱀

 

 

❓분류 : pass!!!

예전에 정답코드를 보고도 이해하지 못했던 문제였는데 스스로 풀어서 기쁘다!

 

❓ 풀이

이 문제의 핵심은 뱀의 길이를 늘렸다 줄였다 할 수 있다는 점이다.

가장 처음 발자취를 남긴 뱀의 위치(꼬리)를 없애줘야 하기 때문에 순서가 중요!

그리고 FIFO해줘야 하므로 QUEUE를 사용해야한다.

 

나는 추후 이동 방향을 결정하는 정보(3 L, 8 D)도 큐를 활용했다.

 

📜나의 코드

from collections import deque

# 게임이 끝나는 시간을 리턴 

# N = 10
N = int(input())
# K = 4
K = int(input())

regions = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(K):
    r, c = map(int, input().split())
    # 사과 2
    regions[r-1][c-1] = 2
# print(regions)
# regions = [[0, 2, 2, 2, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

row, column = 0, 0 # 초기 위치 : 맨 위 맨 좌측 (1행 1열), 뱀의 길이 : 1
regions[row][column] = 1 # 뱀 표시
snake = deque([(0, 0)]) # 뱀의 길이 : 1

# L = 4
L = int(input())

move = deque([])
for _ in range(L):
    X, C = input().split()
    move.append((int(X), C))
# print(move)

# move = deque([(8, 'D'), (10, 'D'), (11, 'D'), (13, 'L')])

# 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

d = 1 # 초기 뱀의 방향 오른쪽
time = 0
while True:
    time += 1

    if move:
        # 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다.
        X, C = move[0]
        if time > X:
            d = (d+1)% 4 if C == 'D' else (d-1)%4
            move.popleft()

    next_r, next_c = row + dr[d], column + dc[d]

    # 2. 벽이나 자신의 몸에 부딪히면 게임 끝
    if not(0<=next_r<N and 0<=next_c<N) or (next_r, next_c) in snake:
    # if not(0<=next_r<N and 0<=next_c<N) or regions[next_r][next_c] == 1:
        break
    else:
        # 1. 몸의 길이를 늘려 머리를 다음칸에 위치시킨다.
        row, column = next_r, next_c
        snake.append((row, column))

        if regions[row][column] == 2:
            # 3. 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
            regions[row][column] = 1

        else:
            # 4. 이동한 칸에 사과가 없다면, 몸의 길이를 줄여 꼬리가 위치한 칸을 비워준다. 즉, 몸 길이는 변하지 않는다.
            regions[row][column] = 1
            r, c = snake.popleft()
            regions[r][c] = 0

print(time)