백준 3190 뱀

문제

뱀

뱀이 벽 또는 자신의 몸에 부딪힐 때까지 걸리는 시간을 구하자

난이도 : Gold4

---

풀이

1. 뱀이 방향을 전환하는 모든 경우를 나눠서 현재 뱀의 방향을 저장
2. 사과가 나타나면 뱀의 머리 좌표를 큐에 저장, 사과가 없다면 큐 popleft (꼬리 좌표 삭제)
3. 뱀의 몸 좌표를 모두 저장하고 있다가 현재 위치가 벽 또는 몸과 일치하면 반복 종료

---

코드

from collections import deque

N = int(input())
K = int(input())
apples = [tuple(map(int, input().split())) for _ in range(K)]
L = int(input())
dirs = deque([tuple(input().split()) for _ in range(L)])

time = 0  # 게임 진행 시간
start = (1, 1)
body = deque([])  # 뱀 몸 좌표 저장
change_times = list(map(lambda x: int(x[0]), dirs))  # 방향 전환 시간
cur_dir = 'R'  # 현재 뱀이 가리키는 방향

while True:
    if start in body or start[0] == N+1 or start[1] == N+1 or start[0] == 0 or start[1] == 0:  # 몸 또는 벽과 부딪힐 때
        break

    if start in apples:  # 사과 위치에 도달하면 머리 좌표 body에 추가
        body.append(start)
        apples.remove(start)  # 먹은 사과 제거
    else:  # 사과가 없으면 꼬리 좌표 pop
        if body:
            body.popleft()
        body.append(start)

    if time in change_times:
        change_dir = dirs.popleft()[1]
        if cur_dir == 'R':
            if change_dir == 'L':
                cur_dir = 'U'  # 오른 쪽으로 가다가 왼 쪽으로 방향 꺾음 <=> 위 방향
                start = (start[0] - 1, start[1])
            else:
                cur_dir = 'D'  # 오른 쪽으로 가다가 오른 쪽으로 방향 꺾음 <=> 아래 방향
                start = (start[0] + 1, start[1])

        elif cur_dir == 'L':
            if change_dir == 'L':
                cur_dir = 'D'  # 왼 쪽으로 가다가 왼 쪽으로 방향 꺾음 <=> 아래 방향
                start = (start[0] + 1, start[1])
            else:
                cur_dir = 'U'  # 오른 쪽으로 가다가 오른 쪽으로 방향 꺾음 <=> 위 방향
                start = (start[0] - 1, start[1])

        elif cur_dir == 'U':
            if change_dir == 'L':
                cur_dir = 'L'  # 위 쪽으로 가다가 왼 쪽으로 방향 꺾음 <=> 왼 방향
                start = (start[0], start[1] - 1)
            else:
                cur_dir = 'R'  # 위 쪽으로 가다가 오른 쪽으로 방향 꺾음 <=> 오른 방향
                start = (start[0], start[1] + 1)

        else:
            if change_dir == 'L':
                cur_dir = 'R'  # 아래 쪽으로 가다가 오른 쪽으로 방향 꺾음 <=> 오른 방향
                start = (start[0], start[1] + 1)
            else:
                cur_dir = 'L'  # 아래 쪽으로 가다가 왼 쪽으로 방향 꺾음 <=> 왼 방향
                start = (start[0], start[1] - 1)

    else:  # 방향을 바꾸는 시간이 아니라면 현재 진행 방향으로 이동
        if cur_dir == 'R':
            start = (start[0], start[1] + 1)
        elif cur_dir == 'L':
            start = (start[0], start[1] - 1)
        elif cur_dir == 'D':
            start = (start[0] + 1, start[1])
        else:
            start = (start[0] - 1, start[1])

    time += 1

print(time)

---

결과

뱀이 사과를 먹은 좌표를 초기화하지 않아서 처음에 실패했다. 꼼꼼하게 문제를 풀 필요성을 느꼈다.