[백준 3190] 뱀

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

문제 분석

• NxN 정사각 보드가 주어진다.
• 뱀의 길이는 1이며, (1,1)에서 오른쪽을 바라본다.
• 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
  • 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다.
• 이 게임이 몇 초에 끝나는지 출력한다.

구현 설계

• 초기 입력 단계, 범위 체크 함수, 방향 전환 함수, 시뮬레이션 부분으로 구분한다.
• 범위 체크의 경우 주어진 좌표가 범위를 벗어나거나, 뱀의 몸통과 부딪히는지 체크하도록 구현한다.
• 방향을 변경하는 경우 미리 dx, dy 배열을 만들어 인덱스만 변경하는 함수를 만들어 구현한다.
• 시뮬레이션의 경우 현재 위치에 dx, dy 배열의 값을 넣은 뒤, 범위 체크 함수로 확인한 뒤 뱀의 몸통에 해당 좌표를 넣는다. 만약 해당 칸에 사과가 없으면 뱀의 꼬리를 삭제한다. 이러한 구현을 위해 deque 자료구조를 사용한다. 방향 지시의 경우 이동하는 횟수를 뽑아내 그 숫자에 해당하는 반복문을 실행한다.

오답 코드

from collections import deque  
  
N = int(input())  
  
apple_num = int(input())  
apple_arr = []  
for i in range(apple_num):  
    apple_arr.append(list(map(int, input().split())))  
  
direction_num = int(input())  
direction_arr = []  
for i in range(direction_num):  
    num, char = input().split()  
    direction_arr.append((int(num), char))  
  
dx = [1, 0, -1, 0]  
dy = [0, 1, 0, -1]  
direction = 0  
  
snake = deque([(0, 0)])  
count = 0  
  
  
def check_valid_range(dx, dy):  
    return (0 <= dx < N and 0 <= dy < N) and (dx, dy) not in snake  
  
  
def change_direction(dir):  
    global direction  
    if dir == 'D':  
        direction = (direction + 1) % 4  
    elif dir == 'L':  
        direction = (direction - 1) % 4  
  
  
for dir in direction_arr:  
    sec = dir[0]  
    stop = False  
    for i in range(sec):  
        count += 1  
        now = snake[-1]  
        new_x = now[0] + dx[direction]  
        new_y = now[1] + dy[direction]  
        if (not check_valid_range(new_x, new_y)):  
            stop = True  
            break        snake.append((new_x, new_y))  
        if [new_x + 1, new_y + 1] in apple_arr:  
            apple_arr.remove([new_x + 1, new_y + 1])  
        else:  
            snake.popleft()  
    if (stop == True):  
        break  
    change_direction(dir[1])  
  
print(count)

뭐가 문제였을까?

• 문제 해석의 오류
  • 주어지는 좌표는 (행, 열)이 아닌 (열, 행)으로 주어진다.
  • 방향 지시의 경우 (8, D), (10, D)가 주어진다면 8번 이동하고 D로 방향을 전환한 뒤 10번 이동하고 D로 방향을 전환하는 것이 아닌, 8번째 루프에서 D로 방향 전환하고 10번째 루프에서 D로 방향을 전환해야 한다.

변경점

• (행, 열)이 아닌 (열, 행)으로 처리하기 위해 dx와 dy 리스트의 이름을 서로 바꿔준다.
• 시뮬레이션은 while 문으로 돌리면서 count를 증가시키는 방법으로 변경한다.
• 방향 전환의 경우 direction_idx 변수가 direction_arr의 길이 값보다 작고, count가 direction_arr[direction_idx][0], 즉 이동 횟수와 동일하면 방향 전환을 실시하고 direction_idx를 1 증가시키는 방법으로 구현하였다.

전체 코드

from collections import deque

N = int(input())

apple_num = int(input())    # 사과 입력
apple_arr = []
for i in range(apple_num):
    apple_arr.append(list(map(int, input().split())))

direction_num = int(input())    # 방향 지시 입력
direction_arr = []
for i in range(direction_num):
    num, char = input().split()
    direction_arr.append((int(num), char))
direction_idx = 0

dx = [0, 1, 0, -1] # 열, 행이므로 반대로 설정
dy = [1, 0, -1, 0]
direction = 0

snake = deque([(0, 0)]) # 뱀이 있는 좌표
count = 0

def change_direction(dir):
    global direction
    if dir == 'D':
        direction = (direction + 1) % 4
    elif dir == 'L':
        direction = (direction - 1) % 4


while True:
    count += 1
    now = snake[-1]
    new_x = now[0] + dx[direction]
    new_y = now[1] + dy[direction]

    if not (0 <= new_x < N and 0 <= new_y < N) or (new_x, new_y) in snake:
        break

    snake.append((new_x, new_y))

    if [new_x + 1, new_y + 1] in apple_arr:
        apple_arr.remove([new_x + 1, new_y + 1])
    else:
        snake.popleft()

    if direction_idx < len(direction_arr) and count == direction_arr[direction_idx][0]:
        change_direction(direction_arr[direction_idx][1])
        direction_idx += 1

print(count)

결과