[Python 파이썬]백준 3190번 - 뱀

2023년 9월 18일

문제 링크 : 3190번 - 뱀

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

---

문제 접근

구글 snake game

이 문제는 완벽하게 이해하지 못하면 접근하기 까다롭다. 차근차근 문제의 요점부터 알아보자.

1. 가로, 세로의 길이가 N인 정사각형 2차원 배열 위에서 뱀이 움직임.
   
   
2. 뱀의 최초 위치는 [0, 0]이며, 최초 길이는 1이다.
   
   
3. 뱀은 시간이 1 만큼 흐를 수록, 현재 진행방향으로 한 칸 움직인다. 이 때, 뱀의 머리가 먼저 앞으로 한 칸 나아가고, 꼬리에 해당하는 부분을 비워둔다.
   
   
4. 뱀은 처음엔 오른쪽으로 움직이며, D 명령이 주어지면 현재 진행방향의 오른쪽으로, L 명령이 주어지면 현재 진행방향의 왼쪽으로 방향을 바꾼다.
   
   
5. 정사각형 2차원 배열의 특정 위치에 사과가 존재한다.
   
   
6. 뱀은 이동하다 사과가 있는 좌표에 도착하면 해당 사과를 먹어 없앤다. 그리고 뱀의 길이가 1 증가하는데, 뱀의 꼬리를 비워두지 않는 식으로 길이가 1 증가시킨다.
   
   예를 들어, 뱀의 길이가 3이고, 현재 [1, 1] , [1, 2] , [1, 3]에 위치한다고 가정, 뱀의 머리는 [1, 3]이고, 현재 진행방향은 오른쪽이라고 가정하자. 그리고 사과는 [1, 4]에 있다고 가정하겠다.
   이 때, 시간이 1만큼 흘러 한 칸 전진하였을 때, 해당 위치에 사과가 있다면 다음과 같은 플로우로 진행될 것이다.
   
   1. 현재 진행방향인 오른쪽으로 머리가 먼저 한 칸 나아간다. 머리만 나아갔으니 현재 뱀이 차지하는 좌표는 [1, 1] , [1, 2] , [1, 3] , [1, 4] 이다. 사과가 없다면 여기서 꼬리에 해당하는 [1, 1] 을 비워, 길이가 3인 뱀을 유지할 것이다.
   
   2. 그러나, 뱀이 사과가 있는 [1, 4]에 머리가 도착하여 사과를 먹었기에 '길이가 1 만큼 늘었음'을 만족시키기 위해, 꼬리를 비워두는 과정을 생략한다.
   
   3. 최종적으로, 머리가 한 칸 뻗어나간 과정만이 유효하니 사과를 먹은 뱀의 현재 길이는 4, 차지하고 있는 좌표는 [1, 1] , [1, 2] , [1, 3] , [1, 4] 가 될 것이다.
   
   
7. 1~6 과정을 게임오버 될 때까지 진행한다. 게임오버 조건은 다음과 같다.
   1. 뱀이 벽에 부딪힌다 = 진행방향으로 1 만큼 전진했을 때, 정사각형 2차원 배열 범위 밖으로 나간다.
   2. 뱀이 자신의 몸에 부딪힌다 = 진행방향으로 1 만큼 전진했을 때, 도착하는 위치가 이미 뱀이 차지하고 있는 좌표중 하나이다.

뱀이 진행을 하는 과정에서, 머리쪽 길이를 1 만큼 증가시키고, 꼬리쪽 부분을 1 만큼 감소시킨다는 부분에 큐 자료구조를 떠올렸다.

리스트 형식으로 뱀이 차지하고 있는 좌표 정보를 저장하면, 꼬리쪽 부분을 1 만큼 감소시킬 때 O(n) 만큼의 시간복잡도가 발생하니 시간초과의 위험성이 있다고 판단되었다.

큐를 이용하면 파이썬 기준, popleft 메소드를 이용해 O(1)의 효율적인 꼬리 부분 삭제가 가능하기에 뱀이 아무리 오랜 시간동안 이동해도 시간제한의 위험에서 벗어날 수 있다고 생각했다.

---

순서도

1. 입력값 입력받고, 2차원 배열 세팅

2. dx, dy 선언한다 [오른쪽, 아래, 왼쪽, 위] 순서로 세팅
    -> dx = [1, 0, -1, 0]
    -> dy = [0, 1, 0, -1]
    dx,dy의 인덱스를 가리키는 forward라는 변수를 선언, 초기값 0. dx = 1, dy = 0을 가리켜 오른쪽을 향하게 함
    만약 처음으로 D가 등장하면 진행방향의 오른쪽으로 방향을 바꾸는 것이니,
    forward를 1 증가시켜, dx = 0, dy = 1을 가리키게 함

3. 뱀의 몸이 차지하는 좌표 정보를 담기 위해 큐로 선언한다.

4. time을 1씩 증가시켜, dx와 dy쌍이 가리키는 방향으로 계속 움직인다. 대신, 다음과 같은 플로우를 지키도록 한다.
    4-1. 머리쪽 길이를 1 증가시킨다
    4-2. 꼬리쪽 길이를 1 감소시킨다.

    만약 [[1,1], [1,2], [1,3]]을 차지하는 길이 3의 뱀이 오른쪽으로 한 칸 움직인다면 다음과 같이 진행될 것이다.
    -1. 큐의 마지막 인덱스 위치에 [1,4]를 append
    -2. 큐의 0번째 인덱스 위치의 [1,1]를 popleft
    -3. 만약 append한 좌표가 이미 뱀이 차지하는 좌표와 같다 or 2차원 배열 범위를 벗어났다 => 게임 종료

5. 해당 위치에 사과가 있으면 머리쪽 길이를 1 증가시킨다. = 사과 위치의 인덱스를 append한다.
    만약 머리쪽 길이가 1 증가됐을 때 추가로 차지하는 위치가 이미 뱀이 차지하는 좌표와 같다 or 2차원 배열 범위를 벗어났다 => 게임 종료

 

---

입력 예제

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

 

위의 입력이 들어왔을 때, 초기 세팅은 다음과 같다.

초기 상태 ( time = 0 )

 

초기 진행방향은 오른쪽이니, 시간 즉 time이 1씩 증가 할 때마다 진행방향으로 뱀이 1씩 나아간다.

 

time = 1

time = 2

time = 3

 

여기서 time이 3일 때, 방향을 오른쪽으로 변화시키는 명령어가 존재한다. ( 3 D )

뱀의 진행방향을 현재 진행방향의 오른쪽으로 바꿔준다.

 

time = 4

진행방향을 오른쪽으로 튼 상태로 1만큼 전진한다.

 

time = 5

진행방향으로 1만큼 전진하니 사과가 있는 좌표에 도착했다. 사과를 먹고 길이를 1 증가시켜준다.

 

time = 6

time = 7

time = 8

time = 9

뱀이 벽에 부딪혔다. (정사각형 2차원 배열 범위 밖으로 나갔다.)

게임이 종료되었으니 게임이 종료된 시점의 time인 9를 출력한다.

 

출력 예제

9

 

---

주의할 점

주의할 점은 다른 분의 글을 인용하겠다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 그 후에 꼬리 길이를 줄이는 것이다. 따라서 꼬리를 줄이기 이전에 뱀이 부딪힐 수 있다. 
• 사과는 먹으면 없어진다.
• 8 D 라는 뜻은 8초가 지난 후(9초가 시작함과 동시)에 오른쪽으로 방향을 튼다는 뜻이다.
• 1행 1열부터 시작이다.

---

전체 코드

from collections import deque
import sys

input = sys.stdin.readline

def solution():
    # 2. dx, dy 선언
    # 오른쪽, 아래쪽, 왼쪽, 위쪽
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    # 현재 움직이는 위치를 가리킬 forward 선언.
    # dx, dy 인덱스 쌍을 가리켜, 현재 이동방향의 기준이 될 것
    forward = 0 

    # 3. 뱀이 현재 차지하고 있는 좌표정보를 담을 큐 형태의 자료구조 선언
    # 뱀의 첫 시작위치는 [0,0]이니 미리 추가해줌.
    snake = deque([[0, 0]])

    L = int(input())
    # 뱀의 방향정보를 담을 큐 선언
    goto_info = deque([])
    for _ in range(L):
        goto_time, goto_forward = map(str,input().split())
        goto_info.append([int(goto_time),goto_forward])
    
    # 게임 경과 시간. 만약 게임오버 된다면, time을 출력해야 한다.
    time = 0

    # 4. time을 1씩 증가시켜, dx와 dy쌍이 가리키는 방향으로 계속 움직인다.
    while(1):
        time += 1
        # 현재 진행방향으로 머리를 한 칸 늘린다.
        head = [snake[-1][0] + dy[forward], snake[-1][1] + dx[forward]]
        
        # 머리를 한 칸 늘렸을 때, 자신의 몸이나 벽에 부딪혔다면 게임종료
        if isGameOver(snake, head):
            return time
        # 아니라면 snake에 정상적으로 append하여 진행방향만큼 1 전진
        else:
            snake.append(head)

        # 만약 사과를 먹지 않았다면 꼬리를 1만큼 제거
        if board[head[0]][head[1]] == 0:
            snake.popleft()
        # 만약 사과를 먹었다면 사과 위치의 값을 1에서 0으로 변경
        # 꼬리는 제거하지 않음
        else:
            board[head[0]][head[1]] = 0

        # 진행방향을 바꿔야하는지 확인
        if goto_info and time == goto_info[0][0]:
            if goto_info[0][1] == "D":
                forward = (forward + 1) % 4
            else:
                if forward == 0:
                    forward = 3
                else:
                    forward -= 1
            goto_info.popleft()
            

# 게임종료 조건을 확인하는 메소드
def isGameOver(snake, head):
    if head in snack:
        return True
    elif head[0] >= N or head[0] < 0 or head[1] >= N or head[1] < 0:
        return True
    else:
        return False
    
if __name__ == "__main__":
    # 1. N, K, 사과위치 입력 받고 2차원 배열 세팅
    N = int(input())
    board = [ [0 for _ in range(N)] for _ in range(N)]
    
    # 사과 위치 세팅. 사과가 있는 곳은 1로 표시한다.
    K = int(input())
    for _ in range(K):
        apple_x, apple_y = map(int,input().split())
        board[apple_x - 1][apple_y - 1] = 1

    print(solution())

 

---

풀이 후기

문제를 이해하고 머리속으로 설계하는 과정이 오래걸렸으나, 잘 이해하고 설계한 내용을 바탕으로 흐름도를 구상하고 코드로 구현하는데에는 어려움이 없었다.

오히려 오류 없이 한 번에 코드 구현에 성공해 '이게 왜 되지..?' 싶었다. 이해 및 설계 단계가 왜 중요한지 알게해주는 문제였다.