백준 3190) 뱀 (골드.4)

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

3190번: 뱀

시뮬레이션 문제로 조건에 따라 이동시키는 문제이다. 

조건을 확인하면 다음과 같다. 

1) 뱀은 0, 0 위치에서 시작하여 처음엔 오른쪽으로 이동한다. 

2) 방향조건이 D일 경우 오른쪽, L일 경우 왼쪽으로 이동한다. 

3) 시간조건은 처음 이동을 시작할 때부터 방향을 바꿀때 까지의 시간을 나타낸다. 

4) 이동할 칸에 사과가 있으면 뱀의 꼬리는 줄어들지 않는다. 

5) 이동할 칸에 사과가 없으면 뱀의 꼬리는 한칸 줄어든다. 

6) 벽이나 자기 자신의 몸을 만나게 되면 게임은 종료된다. 

 

처음 구현한 코드는 다음과 같다. 

코드를 살펴보면 시간(answer)를 1로 초기화하여 이를 이용하여 뱀이 이동한 자리에 시간마다 +1 을하여 정의넣어놓는다. 즉 (지난 시간 +1 = answer)

꼬리부분의 값을 cnt로 설정하고 꼬리가 줄어들때마다 cnt +1 을 하여 다음 꼬리칸을 찾는다. 하지만 이 코드는 주어진 모든 테스트는 통과하였으나 제출 시 통과하지 못했고, 사과가 없는 경우 매번 꼬리칸을 찾기 위해서 최악의 경우 O(n^2)의 find_tail 메서드가 실행되게 된다. 😭

global n, answer , x, y, cnt, d,toward
n = int(input())
apple = int(input())
board = [[0]*n for i in range(n)]

for i in range(apple):
    a, b = map(int, input().split())
    board[a-1][b-1] = -1

answer = 1
y , x = 0, 0
board[0][0] = 1
toward = 0 
cnt = 1
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def search(time, direction) :
    global answer, board, toward, n, x, y, cnt, d
    time -= (answer-1) 
    for _ in range(time) : 
        ny = y + d[toward][0]
        nx = x + d[toward][1]
        answer += 1
        if nx<0 or nx>=n or ny<0 or ny>=n or (board[ny][nx]>0 ) : 
            return True 
        elif board[ny][nx] == -1: 
            board[ny][nx] = answer
        else :
            board[ny][nx] = answer
            t_y, t_x = findTail(cnt)
            board[t_y][t_x] = 0
            cnt += 1
        y = ny
        x = nx
    if direction == 'D':
        toward = (toward+1) % 4
    elif direction == 'L':
        toward = (toward-1) % 4 
    return False 

def findTail(cnt):
    global board
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == cnt : 
                return i, j 
    return 0, 0 

m = int(input())
for i in range(m):
    a, b = map(str,input().split())
    isFinished = search(int(a), b)
    if isFinished:
        break
    elif i == m-1 :
        if d[toward][0] != 0 :
            answer += (y+1)
        elif d[toward][1] != 0 :
            answer += (x+1)

print(answer-1)

 

 

이를 수정하기 위해서 deque를 이용하도록 하였으며, 지나가는 모든 칸을 queue에 넣어놓고 꼬리부분을 찾기 위해서는 popleft()을 이용하도록 수정하였다. 또, 방향을 매번 받을 때마다 함수를 실행하지 않고 모두 dict에 넣어놓고 key를 이용하여 시간이 다 되었으면 방향을 변경하도록 하였다. 벽을 만나거나 뱀 자신의 몸을 만나지 않는 경우 주어진 방향으로 계속해서 이동한다. 

from collections import deque
n = int(input())
apple = int(input())
board = [[0]*n for i in range(n)]
directions = {}
for i in range(apple):
    a, b = map(int, input().split())
    board[a-1][b-1] = 1
m = int(input())
for i in range(m):
    a, b = map(str,input().split())
    directions[int(a)] =  b

answer = 0
queue = deque()
queue.append((0,0))
toward = 0 
x, y = 0, 0 
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def turn(direction) :
    global toward
    if direction == 'D':
        toward = (toward+1) % 4
    elif direction == 'L':
        toward = (toward-1) % 4 

while True : 
    y += d[toward][0]
    x += d[toward][1]
    answer += 1
    if x<0 or x>=n or y<0 or y>=n or (board[y][x]==2):
        break
    if board[y][x] != 1: 
        t_y, t_x = queue.popleft()
        board[t_y][t_x] = 0 
    board[y][x] = 2
    queue.append((y, x))
    if answer in directions.keys():
        turn(directions[answer])

print(answer)

결과적으로 코드의 길이도 간결해지고 시간 복잡도도 줄일 수 있었다.