문제

'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

예제 입력 3

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

예제 출력 3

13

나의 코드

from sys import stdin as s
from collections import deque

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n = int(s.readline().strip())
k = int(s.readline().strip())

apples = []
for i in range(k):
    apples.append(list(map(int, s.readline().split())))

board = [[0] * (n + 1) for _ in range(n + 1)]
for apple in apples:
    board[apple[0]][apple[1]] = 1

l = int(s.readline().strip())
snake_moves = deque()
for i in range(l):
    snake_moves.append(list(s.readline().split()))
for snake_move in snake_moves:
    snake_move[0] = int(snake_move[0])
# 입력 받기 드디어 끝..

# 왼쪽 또는 오른쪽으로 방향을 트는 함수
def turn_dirs(current_dir, left_or_right):
    if left_or_right == "L":
        current_dir = 3 if current_dir == 0 else current_dir - 1
    else:
        current_dir = 0 if current_dir == 3 else current_dir + 1
    return current_dir

# 입력받을 때 사과의 좌표를 표시해 놓은 board에서 현재 위치에 사과가 있는지 확인
def is_apple(board, x, y):
    if board[x][y] == 1:
        return True
    else:
        return False

# 현재 위치가 뱀 몸의 일부인지 확인
def is_snake_body(snake, x, y):
    for (snake_x, snake_y) in snake:
        if snake_x == x and snake_y == y:
            return True

# 매 초의 snake가 어떻게 변화하는지 나타내는 함수
def snake_every_second(snake_moves):
    # 오른쪽을 보고 시작한다고 했으므로 동, 남, 서, 북 순으로 방향 딕셔너리를 선언해 놓음. 시계 방향 편-안.
    dirs = {0: [0, 1], 1: [1, 0], 2: [0, -1], 3: [-1, 0]}
    # 첫 위치는 항상 1, 1
    x, y = 1, 1
    # 오른쪽을 보고 시작한다고 했으므로 dirs에서 0부터 시작함
    current_dir = 0
    # 뱀이 움직일 때마다 FIFO로 튜플을 popleft() 해야 함
    snake = deque([(x, y)])
    # 매 초 뱀이 어떻게 변화하는지 살펴보기 위해 초기에 0초 할당
    second = 0

    while True:
     # 매 초 어떻게 변화하는지 살펴보자.
        second += 1
        # currnet_dir은 이전 초에서 방향을 틀었을 경우 변화하고, 안 틀었으면 그대로임.
        x, y = x + dirs[current_dir][0], y + dirs[current_dir][1]
        
        # out of range인 경우 사망
        if x < 1 or x > n or y < 1 or y > n:
            return second
        # 뱀이 자신의 몸과 박치기 한 경우 사망
        if is_snake_body(snake, x, y):
            return second
        
        # 머리가 새롭게 놓이는 부분을 append
        snake.append((x, y))
        
        # 현재 위치에 사과가 있는가?
        if is_apple(board, x, y):
           # 있으면 사과를 먹어서 없애라.
            board[x][y] = 0
        else:
           # 없으면 꼬리 부분을 줄이자.(머리는 이미 새로운 좌표에 놓아서 몸 길이는 그대로임)
            snake.popleft()
            
        # 현재 초가 방향 전환하는 초일 경우 방향을 틀기
        if len(snake_moves) > 0 and snake_moves[0][0] == second:
            current_dir = turn_dirs(current_dir, snake_moves[0][1])
            snake_moves.popleft()


print(snake_every_second(snake_moves))

시간복잡도

시간복잡도에 의미있는 영향을 미치는 부분이 크게 2가지일 것이라고 생각했다.

• 현재 위치에 사과가 있는지 확인(is_apple 함수를 O(N^2)에서 O(1)으로 개선)
  • 처음에 is_apple 함수를 사과 좌표가 담긴 배열을 순회하며 일일히 사과가 있는지 탐색하는 방식으로 2중 for문으로 짰다가, 최악으로 O(N^2)을 매번 곱해줘야되버렸다. 그래서 미리 board에 사과의 위치를 1로 표시해놓고 (O(K) 소요) 탐색할 때는 x,y 인덱스를 이용하여 O(1)의 시간복잡도로 확인 가능하게끔 바꿨다.
• 반면 is_snake 함수는 사과와 달리 매 초마다 변하기 때문에 사과처럼 미리 board를 만들어서 1을 표시하기보다는, 현재 위치가 자신의 몸과 박치기한 좌표는 아닌지 일일히 뱀 몸의 원소 하나하나 확인했다. (여길 set으로 해결했어야 했다.)

이렇게 하더라도 전체적인 시간복잡도는 O(K + X * 10 ^ 2)이므로 넉넉하다. 이번 문제는 시간복잡도를 걱정해야 하는 문제는 아니었다.

문제를 이해하는 게 제일 어려웠던 문제. 어디서부터가 1초냐?

문제를 이해하고 나서는 막상 생각보다 코드를 짜는게 막 못 짤 정도로 어렵지는 않았다. 근데 문제 이해하는 데 제일 오래 걸렸다. 어디서부터를 1초로 볼 것이냐를 파악하는 게 제일 오래 걸렸다. 처음에는 (1, 1)에 있을 때부터가 1초인 줄 알고 첫번째 테케를 확인해봤는데 맞아 떨어지는 것이었다. 그래서 2번째 테케도 종이에 뱀들을 그려가면서 확인해봤는데 이번에는 안맞아 떨어지는 것이었다. 죽었는데 왜 20초야?! 여기서 30분 헤매다가, (1, 1)에 있을 때가 0초이고 (1, 2)에 갔을 때 1초가 된다는 것을 깨닫고 테케가 맞아떨어지는 걸 확인할 수 있었다.

종이에 그려본 매 초 뱀의 모습과 print된 뱀 모습이 달라서 처음에 헤맸는데 알고 보니 맞게 가고 있는 거였음

종이에 그린 뱀

출력된 뱀

# 1초인데 (1, 1)이 왜 안 없어져?!! 이러면서 처음에 당황했음.
1 초: deque([(1, 1), (1, 2)])
2 초: deque([(1, 1), (1, 2), (1, 3)])
3 초: deque([(1, 1), (1, 2), (1, 3), (1, 4)])
4 초: deque([(1, 1), (1, 2), (1, 3), (1, 4), (1, 5)])
# 알고보니 5초가 됐을 때 현재 좌표에 사과가 없으면 알아서 (1, 1)을 popleft해줘서 문제 없는 거였음.
5 초: deque([(1, 2), (1, 3), (1, 4), (1, 5), (1, 6)])
6 초: deque([(1, 3), (1, 4), (1, 5), (1, 6), (1, 7)])
7 초: deque([(1, 4), (1, 5), (1, 6), (1, 7), (1, 8)])
8 초: deque([(1, 5), (1, 6), (1, 7), (1, 8), (1, 9)])
9 초: deque([(1, 6), (1, 7), (1, 8), (1, 9), (2, 9)])
10 초: deque([(1, 7), (1, 8), (1, 9), (2, 9), (3, 9)])
11 초: deque([(1, 8), (1, 9), (2, 9), (3, 9), (3, 8)])
12 초: deque([(1, 9), (2, 9), (3, 9), (3, 8), (2, 8)])
13 초: deque([(2, 9), (3, 9), (3, 8), (2, 8), (1, 8)])
14 초: deque([(3, 9), (3, 8), (2, 8), (1, 8), (1, 7)])
15 초: deque([(3, 8), (2, 8), (1, 8), (1, 7), (1, 6)])
16 초: deque([(2, 8), (1, 8), (1, 7), (1, 6), (1, 5)])
17 초: deque([(1, 8), (1, 7), (1, 6), (1, 5), (1, 4)])
18 초: deque([(1, 7), (1, 6), (1, 5), (1, 4), (1, 3)])
19 초: deque([(1, 6), (1, 5), (1, 4), (1, 3), (1, 2)])
20 초: deque([(1, 5), (1, 4), (1, 3), (1, 2), (1, 1)])
21

종이에는 1초부터 꼬리 부분이 5초까지 꼬리 부분이 계속 (1, 2)라고 적어놨는데 출력하니까 1초부터 4초까지 꼬리 부분이 계속 (1, 1)이어서 뭐가 잘못된 줄 알았다. 그래서 (1, 1)일 때만 popleft()를 해야하나 고민했는데, 문제 전반적으로는 논리가 맞기 때문에 예외적으로 문제에서 설명하는 뱀의 몸길이보다 초반에는 1만큼 더 긴 걸 허용해줘야 하는 부분인 듯 했다.

마지막 짧은 후기

구현은 문제를 이해하는 것부터 숨막히는 경우가 많은 것 같다. 지금처럼 어디부터가 1초인지 헷갈릴 경우에는 (1, 1)이 0초일 때와 (1, 1)이 1초일 때로 나눠서 빠르게 테케와 부합하는 쪽을 선택했어야 했다.

시간복잡도가 여기서 더 개선될 수 있었다.

그리고 코드를 제출하고 공부하며 깨달은 건데, snake의 몸을 set()으로 선언하고 매초마다 (x, y)가 있는지 확인하면 시간복잡도 O(1)으로 해결할 수 있었다. 다음부터는 배열을 일일히 순회하며 확인해야할 때 set을 적극적으로 활용해보자! set을 쓰면 add랑 remove 메서드로 O(1)의 시간복잡도로 내맘대로 추가하고 삭제하고 할 수 있다.

하여튼 재미있는 문제였다 ㅎㅎ 구현이랑 더 많이 친해졌음 좋겠다. 구현아 나랑 제발 친해져줘 (질척)