백준 온라인 저널, 구현, 자료 구조, 덱, 큐, 정렬/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가 증가하는 순으로 주어진다.

 

 

출력

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

 

 

예제 입력 1

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

예제 출력 1

9

 

예제 입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

21

- 문제 정의 시 설명하고 있는 규칙에 따라 알고리즘을 작성한다.

 

 

 

 

접근 방법

1. 시작 위치 (1, 1)을 snake(큐 자료구조)에 삽입하고 방향 전환 정보가 담긴 리스트는 내림차순으로 정렬한다.

2. 현재 주어진 방향에 따라 이동할 칸에 대한 정보를 head에 담고, snake에서 가장 앞에 있는 원소는 tail에 담는다.

    * 큐는 선입선출 구조를 가지고 있기 때문에 가장 오래전에 삽입한 원소가 가장 앞에 위치하게 된다.

3. head 위치(이동할 위치)에 사과가 있다면 tail는 그대로 남겨두고 snake에 현재 위치를 삽입한다.

4. head 위치에 사과가 없다면 snake에서 tail는 삭제시킨다.

5. 2번 ~ 4번을 반복하다 방향 전환 정보의 가장 마지막 인덱스에 위치한 정보의 시간이 되면 방향 변환 정보를 바꿔준다.

6. 2번 ~ 5번을 반복하다 snake의 head가 snake에 있는 원소와 겹치거나 정해진 지역을 벗어나면 반복문을 끝내고 시간을 출력한다.

 

 

코드

from collections import deque
import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
apples = [list(map(int,sys.stdin.readline().split())) for _ in range(k)]
l = int(sys.stdin.readline())
directions = [sys.stdin.readline().split() for _ in range(l)]


# 시간이 느린 순서대로 정렬 -> 제일 뒤의 인덱스로 확인 후 해당 시간이 지나면 pop
# 시간복잡도 : O(NlogN) 소요
# 만약 정렬을 하지 않고, 인덱스 변수를 설정해 단순히 인덱스에 따른 탐색을 한다면 더 많은 시간을 줄일 수 있다. 주어진 방향 전환 정보는 X가 증가하는 순으로 주어지기 때문이다.
directions.sort(reverse=True, key=lambda x: int(x[0]))

map_ = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(k):
    x, y = apples[i]
    map_[y][x] = 1

steps = [[0, 1], [1, 0], [0, -1], [-1, 0]] # 동/남/서/북
d = 0 # 방향 인덱스
count = 0

snake = deque([])
snake.append([1,1])

while True:
    tail = snake[0]
    head = snake[-1]
    dx, dy = steps[d] # 이동 경로 탐색
    count += 1 # 시간 체크
    
    # 벽 안에 머리가 포함되는지 확인한다.
    if 1<=head[0]+dx<=n and 1<=head[1]+dy<=n:
        # 자기자신의 몸에 부딪히면 게임이 끝난다.
        if [head[0]+dx, head[1]+dy] in snake:
            break
        
        # 방향 전환 정보의 시간이 되면 방향을 전환한다. 주의할 점은 현재 머리의 위치는 방향 정보 시간이 되기 이전의 방향 정보를 반영해야한다는 점이다.
        if len(directions) > 0 and count == int(directions[-1][0]):
            time, dir = directions.pop()
            if dir == 'D':
                d = (d+1) % 4
            elif dir == 'L':
                d = (d-1) % 4
        
        # 사과가 없다면 snake에서 tail을 삭제한다.
        if map_[head[1]+dy][head[0]+dx] != 1:
            snake.popleft()
        # 사과가 있다면 map_에서 사과를 삭제한다.    
        else:
            map_[head[1]+dy][head[0]+dx] = 0
        snake.append([head[0]+dx, head[1]+dy])
        print(snake)

    # 벽에 몸에 부딪히면 게임이 끝난다.
    else:
        break
print(count)

- 위의 코드에서는 방향 전환 정보를 내림차순으로 정렬해 원소를 하나씩 삭제시키며 방향 전환 정보를 받았다. 하지만 그렇게 할 필요 없이 주어진 방향 전환 정보에 대해 앞에서부터 순차적으로 탐색해가며 시간이 지나면 인덱스를 증가시키는 방향으로 식을 짠다면 조금 더 빠르게 동작할 수 있다.

    * 파이썬에서 제공하는 정렬 함수의 시간복잡도 : O(NlogN) 

    * 파이썬에서 리스트 삭제 시간복잡도 : pop()은 O(1) / remove는 O(N)

    * 파이썬에서 인덱스를 통한 탐색 시간 복잡도 ; O(1)

- 문제를 잘 읽고 순서에 따라 잘 정리하는 것이 중요한 문제이다.