[BOJ/백준] 3190 뱀

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
apples = set(tuple(map(int,input().split())) for _ in range(K))
command_cnt = int(input())
# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
flag = True
next_time = commands[0][0]
break_flag = False
while True:
    if flag:
        next_time = commands[ind][0]


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if (next_x,next_y) not in snakes:
            if (next_x,next_y) in apples:
                snakes.appendleft((next_x,next_y))
                apples.remove((next_x,next_y))
            else:
                snakes.pop()
                snakes.appendleft((next_x,next_y))
        else:
            break_flag = True
    else:
        break_flag = True
    if break_flag:
        break



    if snake_times == next_time:
        snake_direction = (snake_direction + commands[ind][1])%4
        ind += 1
        if ind == command_cnt:
            flag = False
print(snake_times)

이 문제는 큐와 스택같은 자료구조에 대해서 알면 쉽게 풀 수 있는 문제이다.

 

물론 나는 오래걸렸다.

 

먼저 여기서는 방향 전환이 왼쪽, 오른쪽 밖에 없다. 만약에 동남서북(0,1,2,3) 형태로 방향을 저장해놓은 상태라면, 왼쪽일때는 -1을 해주고 오른쪽일때는 +1 을 해주고, 4로 나눈 나머지를 구해주면 된다.

 

기본적인 방법은 다음과 같다. snake는 기본적으로 deque 형태로 저장을 해준다.

 

먼저 snake_head를 기준으로 탐색해야한다. 나는 deque에서 왼쪽 즉 처음 들어온부분이 head로 가정했기 때문에, snake[0]을 가져온다. 그리고 snake의 방향에 맞게 진행을 해준다. 만약 범위를 벗어나거나 이미 snake에 있는 위치로 갈시, 예외처리를 해주고, 즉각적으로 멈출수 있게 break_flag를 해주었다.

그리고 둘 중 하나인데 만약에 뱀의 머리가 움직인 위치에 사과가 있을때에는, 뱀의 길이가 늘어난 것이기 때문에 새로운 head의 위치를 snake에 추가해주고, apple를 없애준다.

만약에 사과가 없을때에는 꼬리부분을 없애주고, 새로운 머리부분을 추가해준다.

 

매 타임마다 위와 같이 진행을 해주면 되는데, 여기서 명령어가 주어진다. 여기서 주의할 점은 시간이 끝난뒤 시행되는 것이기 때문에 time을 늘려주는 로직을 이 명령어를 조작하는 부분보다 상위에 두어야한다.

뱀이 움직이 시간이 끝난 시간과 명령어에 들어온 시간이 같으면 명령어 대로 방향을 바꿔준다.

그리고 이 명령어의 길이가 3일때, 만약에 3번째 명령까지 반영해서 방향을 바꿔주었으면 마지막 방향대로 계속 진행을 해야하기 때문에 flag를 통해 예외 처리를 해주었다.

 

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
board = [[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    x,y = map(int,input().split())
    board[x][y] = 1

command_cnt = int(input())

# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
board[1][1] = 2
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
next_time,next_direction = commands[0]
break_flag = True
while True:


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if board[next_x][next_y] != 2:
            if board[next_x][next_y] == 1:
                snakes.appendleft((next_x,next_y))
                board[next_x][next_y] = 2
            else:
                board[next_x][next_y] = 2
                tail_x,tail_y = snakes.pop()
                board[tail_x][tail_y] = 0
                snakes.appendleft((next_x,next_y))
            break_flag = False
    if break_flag:
        break
    break_flag = True



    if snake_times == next_time:
        snake_direction = (snake_direction + next_direction)%4
        if ind < command_cnt-1:
            ind += 1
            next_time,next_direction = commands[ind]

print(snake_times)

위의 내가 했던 부분과 거의 동일하다. 대신 board라는 2차원 리스트에 뱀의 위치와 사과의 위치를 표시해주었다 이렇게 하면, 첫번째 코드에서 썼던 not in snakes와 같은 logN이 걸리는 시간이 좀 더 줄어드는 장점이 있다.