[Algorithm🧬] 백준 3190 : 뱀

문제

보아하니 BFS 를 쓰면 되겠군 이라는 생각이 들어서 실행에 옮겼다.
근데 일단 문제가 한쪽 방향으로 움직이면 그 쪽으로만 계속 움직이는거라,
큐를 쓸 필요는 없을 것 같아서 큐는 쓰지 않았고,

대신 지금 머리의 위치 head 를 가지고 있으면 되겠다 싶어서 head 만 가지고 시작을 했다.
-> 근데 그랬더니 꼬리를 줄일 때, 방향이 틀어져 있었다면 문제가 생겨서 tail 을 저장하려고 했음.
-> 그러면 몸의 길이가 10인데 막 방향을 틀었을 때 tail 이 움직이는 방향은 지금 head 가 움직이는 방향이 아니라 틀기 전 방향으로 움직여야해서... 연산이 귀찮아짐
-> 그냥 현재 몸인 곳 전체를 body 에 넣어서 생각했다. tail 줄일 때 pop(0) 해서 걔만 빼면 되니깐!!

헷갈린점 1

8 D
10 D
이렇게 되어 있는게 8초동안 가고 오른쪽으로 틀고, 또 거기서 10초 동안 가고 오른쪽으로 트는 거인줄 알았다..
앞에 있는게 시작 시간 기준으로 n 초 뒤에 트는거라서 내가 한대로 하면
8 D
2 D
로 배열을 가공하는게 맞아서 가공하고 진행했다.

헷갈린점 2

중간에 방향 틀 때 자기 몸이나 벽에 안부딪혔으면
맨 마지막에 방향을 틀고도 그 방향으로 쭉 가는것까지 생각해야함.

import sys
readl = sys.stdin.readline

def BFS():
    # q = deque([(1, 1)])

    direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] # dir + 1 하면 오른쪽으로 틀고 -1 하면 왼쪽으로 틀고.
    dir = 0 # 초기엔 오른쪽.


    head = (1, 1)
    body = [(1, 1)]
    board[1][1] = 2 # 자기 자신은 2
    time = 0
    
    for t, d in move:

        # 오른쪽으로 X 만큼
        for i in range(t):
            x, y = head
            nx, ny = x + direction[dir][0], y + direction[dir][1]
            ntime = time + 1

            # 벽이거나 자기자신이면 return
            if board[nx][ny] == 9 or board[nx][ny] == 2:
                return ntime

            # head, body, time 갱신.
            head = (nx, ny)
            body.append(head)
            time = ntime

            # 사과가 아니면 몸 길이를 줄임.
            if board[nx][ny] != 1:
                tail = body.pop(0)
                board[tail[0]][tail[1]] = 0
            
            board[nx][ny] = 2

            # for i in range(N + 2):
            #     print(board[i])
            # print()

        dir = (dir + 1) % 4 if d == "D" else (dir - 1) % 4



    return -1

N = int(readl())
K = int(readl())

# 벽은 9
board = [[9] + [0] * (N) + [9] if 1 <= i <= N else [9] * (N + 2) for i in range(N + 2)]

# 사과는 1
for _ in range(K):
    r, c = map(int, readl().split())
    board[r][c] = 1

# move
L = int(readl())
moves = [readl().split() for _ in range(L)]

# 처음에 움직인 시점으로부터 몇 초 움직이고 트는건 줄 알았는데,
# 시작 시간으로부터 17초 후에 튼다 이런 식이어서
# 앞에 방향 트는 시간을 빼서 가지고 있어야 내가 원하는 대로 나오는 거였음.
move = []
move.append([int(moves[0][0]), moves[0][1]])

for i in range(1, L):
    move.append([int(moves[i][0]) - int(moves[i - 1][0]), moves[i][1]])

# 만약에 마지막인데 아직 부딪힌 적이 없으면 해당 방향으로 쭉 가서 부딪힐 것임.
move.append([N, 'X'])

print(BFS())