3190 - 뱀

 

---

 

문제

https://www.acmicpc.net/status?user_id=whipbaek&problem_id=3190&from_mine=1 

채점 현황

 

풀이

처음에 헷갈렸던거

1. 가장 좌측 상단은 [1, 1] 이다. [0, 0] 이 아니다.

2. 시간과 방향이 입력될 때 8 D, 10 D 이런식으로 들어오는데 시간초는 절대적인 시간을 의미한다. 8초가 끝난 후에 이후 추가적인 10초가 아니라 '시작 시간' 이후의 시간을 받는것이니 헷갈리지 말자.

 

 

 

풀이 처음에는 방향을 설정해줬다. L을 받으면 왼쪽으로 틀고, D를 받으면 오른쪽을 틀도록 dx, dy를 설정했다.

 

이후에는 사과의 위치와 뱀의 위치를 저장하는 2차원 배열을 각각 만들었다.

* 생각해보니 이 두개의 정보는 한 배열에 그냥 담아도 되었을 거 같긴한데.. 그냥 헷갈리기 싫어서 두개로 나뉘었다.

 

방향 같은 경우에는 시간초에 따라서 변할 수 있도록 설정했고, 머리가 이동하는 다음칸이 벽이거나 뱀의 몸이라면 탐색을 그만두도록 설정했다.

 

마지막으로 문제의 핵심인 사과 여부에 따른 뱀의 위치 처리 과정이다.

나는 덱을 하나 만들어서 뱀의 머리 ~ 꼬리까지 좌표를 모두 저장해놨다. (머리가 덱의 가장 앞, 꼬리가 가장 뒤다.)

벽이나, 몸이 아닐경우에 머리는 무조건 다음칸으로 이동하기 때문에 덱의 가장 앞에 새 좌표를 저장해준다. 또한 뱀의 위치를 저장하는 2차원 배열에도 저장해준다. 이 과정 같은 경우에는 사과의 유무와 전혀 상관없다. 머리는 항상 다음칸으로 이동하기 때문이다.

 

만약 이동할려는 곳으로 사과가 있다면 꼬리의 위치가 변하지 않기때문에 (몸이 늘어나기 때문) 사과만 먹어 처리해주면 된다.

 

만약 사과가 없다면, 덱에서 가장 뒷부분인 꼬리 부분을 pop한다음에 뱀의 위치에서 제거해주면 된다. 꼬리는 다음칸으로 이동해야하기 때문이다. (사실상 머리가 다음칸으로 이동하였으므로 꼬리는 삭제만 하면 되는 구조다.)

 

이 과정을 반복해주면 된다.

 

코드

from collections import deque

# 방향 변환
def getdir(d, turn):
    if turn == 'L':
        if d == 0:
            return 3
        else:
            return d-1
    else:
        if d == 3:
            return 0
        else:
            return d+1

# 방향 순서 ← ↑ → ↓
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

n = int(input())
k = int(input())

# 사과의 위치를 저장한다.
board = [[0] * n for _ in range(n)]

# 뱀의 위치를 저장한다.
snake = [[0] * n for _ in range(n)]
snake[0][0] = 1
position = deque()
position.append((0, 0))

# 사과의 위치를 입력 받는다.
for _ in range(k):
    a, b = map(int, input().split())
    board[a-1][b-1] = 1


l = int(input())

# 첫 방향 위치
direction = 2
x = y = 0

times = []

for _ in range(l):
    time, d = map(str, input().split())
    times.append([int(time), d])
i = 0
# 시간순으로 정렬해준다.
times.sort()

time, turn = times.pop(0)
while True:
    if i == time:
        direction = getdir(direction, turn)
        if times:
            time, turn = times.pop(0)

    nx = x+dx[direction]
    ny = y+dy[direction]
    # 다음칸이 범위 안에 들어오면서, 뱀의 몸이 아닌경우에
    if 0 <= nx < n and 0 <= ny < n and snake[nx][ny] == 0:

        # 이동하는 곳의 위치를 체크 및 deque에 넣어준다.
        snake[nx][ny] = 1
        position.appendleft((nx, ny))
        # 사과가 있다면 먹어준다
        if board[nx][ny] == 1:
            board[nx][ny] = 0

        # 사과가 없다면 뱀의 꼬리를 삭제해준다.
        else:
            lx, ly = position.pop()
            snake[lx][ly] = 0

        x = nx
        y = ny

    # 부딪혔다면 게임을 끝내준다.
    else:
        break

    i+=1

print(i+1)

 

후기

 

무난한 문제였던 거 같다. 포인트는 덱의 활용 아닐까 싶다.