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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력
n = int(input().strip())
# 보드의 상하좌우 끝 벽 = -1
# 빈 칸 = 0
# 사과 = 1
board = [[-1]*(n+2)] + [[-1] + [0]*n + [-1] for _ in range(n)] + [[-1]*(n+2)]
# 사과 입력
k = int(input().strip())
for _ in range(k):
    r, c = map(int, input().split())
    board[r][c] = 1
# 방향 변환 정보 입력
L = int(input().strip())
dir_cmd = dict()
for _ in range(L):
    x, c = input().split()
    dir_cmd[int(x)] = c


def move_snake(row, col, dir, snake_body, time):
    while True:

        """
        print('='*30)
        print("현재 초", time)
        print("뱀의 궤적", snake_body)
        print('='*30)
        for _ in board:
            print(_)
        """

        # 방향 전환
        if time in dir_cmd and dir_cmd[time] == 'L':
            # print("왼쪽으로 방향전환")
            # (0, 1) -> (-1, 0)
            # (0, -1) -> (1, 0)
            # (1, 0) -> (0, 1)
            # (-1, 0) -> (0, -1)
            dir = [-dir[1], dir[0]]
        elif time in dir_cmd and dir_cmd[time] == 'D':
            # print("오른쪽으로 방향전환")
            # (0, 1) -> (1, 0)
            # (0, -1) -> (-1, 0)
            # (1, 0) -> (0, -1)
            # (-1, 0) -> (0, 1)
            dir = [dir[1], -dir[0]]
        next_row = row + dir[0]
        next_col = col + dir[1]

        # 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다
        if board[next_row][next_col] == -1 or (next_row, next_col) in snake_body:
            # 다음 이동 시 게임이 끝날 것이므로 time + 1
            return time+1

        # 이동한 칸에 사과가 있다
        if board[next_row][next_col] == 1:
            # 사과 없애주기
            board[next_row][next_col] = 0
            # 업데이트
            row = next_row
            col = next_col
            snake_body.append((row, col))
        # 이동한 칸에 사과가 없다
        else:
            # 꼬리가 위치한 칸을 비워준다
            tail_row, tail_col = snake_body.popleft()
            # 업데이트
            row = next_row
            col = next_col
            snake_body.append((row, col))

        time += 1


# 초기 뱀의 위치는 (1, 1)
# snake_body = 뱀의 지금까지 궤적을 저장한 큐
# snake_body의 길이가 뱀의 길이
snake_body = deque([(1, 1)])
# 초기 dir는 오른쪽
print(move_snake(1, 1, [0, 1], snake_body, 0))

---

🧂아이디어

구현

• board
  • 상, 하, 좌, 우 끝 벽들은 -1로 표시한다.
  • 사과는 1로 표시한다.

• 뱀
  • python의 deque를 사용하여 선입선출 큐로 유지한다.
  • deque 안에 들어가있는 좌표들은 뱀의 몸통이 차지하고 있는 위치들이다.
  • 꼬리가 위치한 칸을 비워줄 때에는 popleft()를 이용하면 된다.

• 사과
  • 뱀이 먹었다면 반드시 없애줘야 한다! (3190번문제 질문 탭에 들어가서 보면 이걸 하지 않아서 틀리는 경우들이 많은 것 같다)

• 시간

  • 뱀이 이동을 할 때, 1초가 걸린다.
  • 다음 이동 시, 벽에 부딪히거나 뱀의 몸통에 닿는다면 현재 초 + 1을 return해줘야 한다.

• 문제에서 주어진 예제 입력 1을 입력했을 때 위 코드에서 주석을 해제한 뒤 출력된 결과들을 보면

(입력)
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
(출력)
==============================
현재 초 0
뱀의 궤적 deque([(1, 1)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 1, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 1
뱀의 궤적 deque([(1, 2)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 1, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 2
뱀의 궤적 deque([(1, 3)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 1, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 3
뱀의 궤적 deque([(1, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 1, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 4
뱀의 궤적 deque([(2, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 1, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 5
뱀의 궤적 deque([(2, 4), (3, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 6
뱀의 궤적 deque([(3, 4), (4, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 7
뱀의 궤적 deque([(4, 4), (5, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
==============================
현재 초 8
뱀의 궤적 deque([(5, 4), (6, 4)])
==============================
[-1, -1, -1, -1, -1, -1, -1, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 1, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, 0, 0, 1, 0, 0, 0, -1]
[-1, 0, 0, 0, 0, 0, 0, -1]
[-1, -1, -1, -1, -1, -1, -1, -1]
9

• 틀렸습니다 2개: 똑같은 코드였는데 실수로 두번 제출함 ^0^
  • 틀렸던 이유
  • 처음에는 board에 뱀을 1로 표시하고, 사과를 2로 표시했었는데 뱀을 따로 표시할 필요가 없고 deque로 뱀의 몸통 정보를 유지하면 된다는 것을 깨닫고 board에 사과만 1로 표시했음.
  • 이때, board[1][1]에 초기 뱀의 위치를 넣어주면서 board[1][1] = 1로 표시했었는데 이걸 지워주지 않아서 생긴 문제였음
• 런타임에러: 구현상의 문제였음