문제 링크: https://www.acmicpc.net/problem/3190

📋 문제 설명

사과가 없을 때는 위 사진과 같이 머리를 한 칸 앞에 위치한 뒤, 꼬리가 있던 칸을 비운다.
만약 위 상황에서 (1, 2)에 사과가 있다면 1번과 2번의 과정만 수행된다. (꼬리가 있던 칸을 비우지 X)

✏️ 예제

🧐 어떻게 구현할까?

• 자료구조 덱(deque)를 사용
  • 한 쪽으로 원소(좌표 값)를 추가 → 뱀이 몸을 늘려 머리를 다음 칸에 위치하는 것을 표현
  • 다른 한 쪽에서 원소를 제거 → 꼬리가 위치한 칸을 비우는 것을 표현
• 게임 종료 상황 구현
  • 벽에 부딪힘 → 현재 좌표가 0보다 작거나, N보다 큼
  • 자기자신의 몸에 부딪힘 → 덱에 동일한 원소가 존재
• 방향 변환 구현
  • BFS, DFS에서 했던 것처럼 direction 배열을 활용

🐍 전체 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input()) # 보드의 크기

k = int(input()) # 사과의 개수
apples = []
for _ in range(k):
    x, y = map(int, input().split())
    apples.append((x, y)) # 튜플 형태로 배열에 저장

l = int(input()) # 방향 변환
move_sec = [] # 몇 초에 하는지?
move_dir = [] # 방향 (L or D)
for _ in range(l):
    s, d = input().split()
    s = int(s)
    move_sec.append(s)
    move_dir.append(d)

d = deque() # 자료구조 덱을 활용
cnt = 0 # 시간
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 방향

# 초기 좌표를 덱에 넣고 시작, 방향도 초기화
cur = (1, 1)
dir_idx = 0
dir = direction[dir_idx]
d.append(cur)

while(True):
    cnt += 1
    x, y = cur[0], cur[1]
    dir_x, dir_y = dir[0], dir[1]
    next = (x + dir_x, y + dir_y) # 뱀의 머리가 위치할 좌표

    # 벽에 부딪히거나 자신의 몸에 부딪힘
    if next[0] > n or next[0] < 1 or next[1] > n or next[1] < 1 or next in d:
        break

    # 계속 진행
    d.append(next) # 오른쪽에 삽입, pop은 왼쪽에서 해야함
    if next not in apples: # 이동한 칸에 사과가 없다면
        d.popleft()
    else:
        apples.remove(next)

    cur = next

    # 방향 전환
    if cnt in move_sec:
        idx = move_sec.index(cnt)
        move = move_dir[idx]
        if move == 'D':
            dir_idx = (dir_idx + 1) % 4
            dir = direction[dir_idx]
        else: # move == 'L'
            dir_idx = (dir_idx - 1) % 4
            dir = direction[dir_idx]

print(cnt)

🥲 왜 틀렸는가?

처음에 이동한 칸에 사과가 있을 경우 사과를 없애는 코드를 구현하지 않았다.

if next not in apples: # 이동한 칸에 사과가 없다면
    d.popleft()
else:
    apples.remove(next)

처음 풀 때는 else 문을 작성하지 않았었다.
그렇게 되면 뱀이 방향 전환을 하며 사과가 있었던 좌표를 재방문할 수 있는데, 그렇게 되면 몸의 길이가 또 한 번 더 길어진다.

굿 ^ㅅ^ bb

🪴 피드백

• 방향 전환 관련 변수로 dir_x, dir_y 등을 사용했는데 보편적으로 dx, dy를 사용한다.
• 방향 전환을 구현하면서 처음에는 조건문으로 마지막 원소일 때 첫 번째 원소로 가도록 하드코딩을 하였는데, % 나머지 연산을 사용하여 더 깔끔하게 코드를 작성할 수 있다.