[백준] 3190번 - 뱀 (+ 파이썬)

코드를 잘 짰는지는 모르겠지만, 너무 많이 틀렸어서 틀린 부분과 풀이 방법을 기록하기 위해 이 글을 쓴다. ("내가 다 해줬잖아..왜 안돼.."를 가장 많이 외치게 했던 문제였다..)

문제

문제 내용: https://www.acmicpc.net/problem/3190

요약

• 'Dummy' 라는 뱀이 기어다니면서 사과를 먹는 도스 게임이 있다.
• 보드의 크기, 사과의 개수, 사과의 위치, 회전하는 횟수, 회전하는 시간&회전 방향을 입력받는다.
• 첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

코드

• 시간 추가 → 이동 → 생사 확인 → 방향 바꿔주기(이동x) → 꼬리 없애기 or 사과먹기
  위의 과정을 반복하고, "생사 확인"에서 죽는 조건에 해당하면 live 변수가 false가 되면서 while 반복문이 종료된다.
• snake_pos가 현재 뱀의 위치이다. 맨 뒤의 아이템이 머리 위치에 해당하고, 맨 앞의 아이템이 꼬리의 위치에 해당한다.
• apple_positions는 사과의 위치를 모아놓은 배열이다.
• turn_times는 회전하는 시간을 모아놓은 배열이다. 현재 시간이 turn_times에 있다면 방향을 바꾼다. 이동은 다음 번에 한다.(게임 시작 시간으로부터 X초가 끝난 뒤에 회전하는 것)

import sys
import itertools
from collections import deque

time = 0
snake_pos = deque([(1, 1)]) # 꼬리가 맨 앞, 머리가 맨 뒤

live = True
directions = ["up", "right", "down", "left"]
dir_index = 1
def turn_snake(dir):
    global dir_index
    # 방향 바꾸기
    if dir == "L":
        dir_index = (dir_index - 1) % 4
    if dir == "D":
        dir_index = (dir_index + 1) % 4
        
def move_snake(dir):
    global live
    global snake_pos
    head_pos = snake_pos[-1]
    if dir == "right":
        snake_pos.append((head_pos[0],head_pos[1] + 1))
    elif dir == "left":
        snake_pos.append((head_pos[0],head_pos[1] - 1))
    elif dir == "up":
        snake_pos.append((head_pos[0] - 1,head_pos[1]))
    elif dir == "down":
        snake_pos.append((head_pos[0] + 1,head_pos[1]))


board_size = int(sys.stdin.readline().strip())

apple_num = int(sys.stdin.readline().strip())
apple_positions = []
for i in range(apple_num):
    apple_position = sys.stdin.readline().strip()
    row = int(apple_position.split()[0])
    col = int(apple_position.split()[1])
    apple_positions.append((row, col))

turn_num = int(sys.stdin.readline().strip())
turn_times = []
dirs = []
for i in range(turn_num):
    turn = sys.stdin.readline().strip()
    turn_times.append(int(turn.split()[0]))
    dirs.append(turn.split()[1])

while live == True:
    time += 1
    
    # 이동
    move_snake(directions[dir_index])

    # 생사 확인
    if (snake_pos[-1][0] < 1) or (snake_pos[-1][0] > board_size) or (snake_pos[-1][1] < 1) or (snake_pos[-1][1] > board_size):
        live = False
    if len(snake_pos) > 1 and snake_pos[-1] in deque(itertools.islice(snake_pos, 0, len(snake_pos)-1)):
        live = False
        
    # 회전
    if time in turn_times:
        time_index = turn_times.index(time)
        turn_snake(dirs[time_index])
    
    # 꼬리 없애기 or 사과 먹기
    if snake_pos[-1] not in apple_positions:
        snake_pos.popleft()
    else: 
        apple_positions.remove(snake_pos[-1])

print(time)

틀렸던 이유들

반례모음: https://www.acmicpc.net/board/view/56469

1. 사과를 제거하지 않아서

이 이유로 틀린 사람들이 많은 것 같다. 처음에는 없애지 않아도 되지 않나 싶었는데, 먹은 사과를 또 먹을 수도 있기 때문에 없애주어야 한다.
사과를 제거하지 않으면, 반례모음의 5번 케이스에서 다른 답이 나온다. 이미 먹은 사과를 또 먹어서 길이가 길어졌기 때문에, 자기 자신의 꼬리와 만나 죽게 된다.

2. 꼬리를 없앤 후에 생사 확인을 해서

이동한 후에 바로 죽었는지 확인을 해야하는데, 머리 이동하고 사과가 없으면 꼬리를 없앤 후에 생사 확인을 했다. 머리가 꼬리를 만나면 죽어야 하는데, 그 경우를 다루지 못해 다른 결과가 나왔다. 그래서 아래와 같은 순서로 코드를 변경해주었다.

전: 시간 추가 → 이동 → 방향 바꾸기(이동x) → 꼬리 없애기 or 사과먹기 → 생사 확인
후: 시간 추가 → 이동 → 생사 확인 → 방향 바꾸기(이동x) → 꼬리 없애기 or 사과먹기

3. 머리와 꼬리의 위치를 변수에 할당한 경우, 이동 후 변경을 안해줘서

처음에 코드를 짤 때 아래 head_pos와 tail_pos처럼 머리와 꼬리의 위치를 변수에 할당한 후 생사 확인을 할 때 사용했다.
그런데 머리를 늘려서 이동한 후 머리와 꼬리 위치를 할당하였기 때문에, 그 후에 꼬리를 자르게 되었을 때를 반영하지 않는다. 따라서 뱀의 꼬리가 실제 위치와 달라지는 문제가 발생하여, 원래 죽어야하는데 안죽는다거나 죽어야하는데 안죽는 그런 경우가 생긴다.

while live == True:
    time += 1
    # 이동
    move_snake(directions[dir_index])
    
    # 머리와 꼬리 위치
    head_pos = snake_pos[-1]
    tail_pos = snake_pos[0]

    # 회전
    if time in turn_times:
        time_index = turn_times.index(time)
        turn_snake(dirs[time_index])
	
    # 사과 못 먹으면 꼬리 자르기
    if head_pos not in apple_positions:
        snake_pos.popleft()
    
    # 생사 확인
    if (head_pos[0] < 1) or (head_pos[0] > board_size) or (head_pos[1] < 1) or (head_pos[1] > board_size):
        live = False
    if len(snake_pos) > 1 and head_pos == tail_pos:
        live = False

4. 종료 조건이 잘못 되어서

뱀은 벽 또는 자기 자신의 몸과 부딪히면 죽는다. 그런데 처음에 잘못 이해하고, 꼬리를 만날 때만 죽게 했더니 틀렸다.

전: if len(snake_pos) > 1 and head_pos == tail_pos:
        live = False
        
후: if len(snake_pos) > 1 and snake_pos[-1] in deque(itertools.islice(snake_pos, 0, len(snake_pos)-1)):
        live = False

그래서 몸통의 위치를 모아놓은 배열안에 머리의 위치가 있다면 죽도록 변경했다.
(deque에서 slice가 필요한 경우 itertools.isslice를 사용한다.)
다른 해결 방법들을 보니 맞는 조건일때만 패스하고, 그 외(else)는 죽게 했던데, 그 방법이 좋은 것 같다. 죽는 조건을 적는 게 더 까다로운 것 같아서 살아있을 때에만 패스하는 방법으로 변경해봐야겠다.