백준 / 골드 4 / 3190. 뱀

생각해봅시다!

• 빡구현 문제라서 여러모로 신경쓸 점이 많습니다.
• 사과를 먹으면 뱀 길이가 늘어난다?? 뱀이 자기자신의 몸과 부딪히면 게임이 끝난다?
  • 뱀의 길이가 늘어나면, 한 번에 여러 칸에 위치해 있을 수 있겠죠.
  • 이때 위치 정보를 어떻게 저장하고 관리해 둘 지 고민해야 합니다.
• 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다?? 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다??
  • 머리와 꼬리를 가진 자료구조... 떠오르시나요?
  • 한쪽에서 데이터를 삽입하고, 반대쪽에서 데이터를 꺼내오는 자료구조 기억나시죠?

입력 받기

N = int(input())    # 보드의 크기
K = int(input())    # 사과의 개수

# 사과의 위치
apples = set()         
for _ in range(K):
    a, b = map(int, input().split())
    apples.add((a - 1, b - 1))
    
L = int(input())    # 뱀의 방향변환 정보
comm_queue = deque() # 모든 방향변환 정보를 담은 큐

# 시간 및 명령
for _ in range(L):
    # 방향이 바뀌는 시간 및 시계/반시계 여부
    time, command = input().split()
    comm_queue.append((int(time), command))

• 사과의 위치는 set으로 관리하도록 하겠습니다.
  • 나중에 x행 y열에 도착했을 때, if (x, y) in apples을 이용해 사과의 존재 여부를 확인할 수 있습니다.
  • set (집합)에 특정 위치가 있는지 확인하는 연산도 $O(1)$, 원소를 삭제하는 연산도 $O(1)$입니다.
  • 그래서 칸에 사과가 있는지를 확인하고, 사과를 먹어버리는 과정을 빠르게 구현할 수 있습니다.
  • 문제의 예제 입력은 1행 1열부터 시작하지만, 저흰 0번부터 시작하게끔 구현할 거니 (a - 1, b - 1)로 빼 줘야 합니다.
• 뱀의 방향 전환 정보는 큐로 관리하도록 하겠습니다.
  • 흔히 큐를 활용하실 때 큐에서 맨 앞 원소를 꺼내는 것만 생각하시는데...
  • 하지만 맨 앞 원소를 안 꺼내고, 확인만 하는 것도 가능합니다.
  • comm_queue[0]을 이용해 방향을 바꿀 시간을 확인하고, 아직 안 됐으면 놔두고, 바꿀 시간이 됐을 때만 꺼내면 됩니다.
  • 문제에서 방향 전환 정보는 시간이 증가하는 순으로 주어진다라고 했으니, 정렬을 하거나 우선순위 큐를 쓸 필요는 없습니다.

필요한 변수 정의

# 뱀 위치 이동
def gameplay():
    curr_time = 0   # 지금 몇 초?
    head_x = 0      # 머리의 위치 - 몇행?
    head_y = 0      # 머리의 위치 - 몇열?
    
    # 현재 뱀이 존재하는 칸의 모든 좌표
    snake_queue = deque([(0, 0)])
    
    # 이동 방향 (순서대로 우 -> 하 -> 좌 -> 상)
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    face = 0        # 우회전이면 +1, 좌회전이면 -1                       

	# 하단코드에 계속

• curr_time은 게임의 경과 초, head_x 및 head_y는 뱀의 머리의 좌표입니다.
• snake_queue는 현재 뱀이 존재하는 칸의 모든 좌표를 담는 큐입니다.
  • 맨 처음엔 뱀의 길이가 1이며 (0, 0) 칸에 위치해 있기 때문에, 원소는 (0, 0)만 두면 됩니다.
  • 일단 뱀이 새로운 칸을 방문하면 (행, 열) 튜플을 인큐할 거고,
  • 뱀이 특정 칸에서 벗어나면 디큐가 이루어진다는 점만 기억해 둡시다.

• dx, dy 리스트는 뱀이 다음으로 이동할 칸을 계산하는 데 사용합니다.
  • 아래 그림처럼 face에 따라 뱀이 쳐다보는 방향이 달라집니다.
  • 뱀이 우회전하면 face가 1 증가(우 -> 하 -> 좌 -> 상)하고, 좌회전하면 1 감소(우 -> 상 -> 좌 -> 하)하도록 구현합니다.

자 이제 게임을 시작해볼까~?

# 게임이 언제 끝나는지 반환
def gameplay():
    # 위 코드에서 이어짐
    while True:
        curr_time += 1
        
        # 뱀 위치 이동
        nx, ny = head_x + dx[face], head_y + dy[face]
        if nx < 0 or N <= nx or ny < 0 or N <= ny:
            return curr_time    # 벽에 부딪힘 -> 게임 끝!
        if (nx, ny) in snake_queue:
            return curr_time    # 뱀에 부딪힘 -> 게임 끝!
        snake_queue.append((nx, ny))    # 머리의 위치를 큐에 추가
        head_x, head_y = nx, ny
        
        # 사과가 있는 경우
        if (head_x, head_y) in apples:
            apples.remove((head_x, head_y))
        else:
            snake_queue.popleft() # 꼬리의 위치를 큐에서 빼기
                    
        # 시간이 된 경우, 방향을 회전한다
        if comm_queue and comm_queue[0][0] == curr_time:
            command = comm_queue.popleft()[1]
            if command == "L": # 좌회전
                face = (face - 1) % 4
            else: # 우회전
                face = (face + 1) % 4

• 우선 무한반복 while True를 이용해 게임을 구현하겠습니다. 1초가 지날 때마다 while문을 1번 돌게 됩니다.
  • curr_time += 1로 시간을 재는 중입니다.

1. 뱀 움직이기

• 일단 뱀이 이동을 해야 합니다!
• 현재 바라보는 위치에 맞게, 다음으로 이동할 좌표 nx, ny를 구합니다.
  • face에 따라 바라보는 위치가 달라짐에 유의하세요.
• nx, ny가 $N \times N$ 범위를 벗어나면, 벽에 부딪혀 게임이 끝납니다.
• (nx, ny)가 자기자신의 몸과 부딪히면, 게임이 끝납니다.
  • snake_queue에 (nx, ny) 좌표가 존재하는지 확인하면 됩니다.
• 게임이 끝나면 게임이 종료된 시점의 시간을 반환합니다.
• 문제가 없으면 head_x, head_y를 nx, ny로 갱신합니다.
• 이때 머리의 새로운 위치를 snake_queue에 넣는 것도 잊지 말아야 합니다

2. 사과 여부 확인하기

• 사과가 없는 경우, 문제에서 꼬리가 위치한 칸을 비워줘야 한다고 명시했습니다.
  • 꼬리가 위치한 칸은 현재 뱀이 위치한 칸 중, 제일 먼저 방문한 칸이 됩니다.
  • 즉 snake_queue에서 디큐를 하면, 제일 먼저 방문한 칸을 꺼낼 수 있겠죠!
  • snake_queue.popleft() 메서드로 해 주면 됩니다.
• 사과가 있어서 먹는 경우, 사과의 좌표를 저장해 둔 apples 집합에서 해당 좌표를 삭제합니다.
  • 사과가 있는 경우 꼬리가 움직이지 않으므로, .popleft() 하지 않습니다.

3. 회전하기

• 매번 comm_queue의 맨 앞 원소를 확인해, 회전할 시간이 됐는지 확입니다.
• 시간이 됐으면, comm_queue에서 값을 꺼냅니다.
• 좌회전은 1을 빼고 우회전은 1 더해주면 됩니다.
  • dx, dy 리스트의 길이가 4였으니, 4의 나머지로 구해야 인덱스를 벗어나지 않습니다.

4. 무한반복

• 무한반복하다보면 언젠간 벽이나 자기 자신을 쳐 버립니다. 계속 반복합시다~

풀이

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())    # 보드의 크기
K = int(input())    # 사과의 개수

# 사과의 위치
apples = set()         
for _ in range(K):
    a, b = map(int, input().split())
    apples.add((a - 1, b - 1))
    
L = int(input())    # 뱀의 방향변환 정보
comm_queue = deque() # 모든 방향변환 정보를 담은 큐

# 시간 및 명령
for _ in range(L):
    time, command = input().split()
    comm_queue.append((int(time), command))
    
# 게임이 언제 끝나는지 반환
def gameplay():
    curr_time = 0   # 지금 몇 초?
    head_x = 0      # 머리의 위치 - 몇행?
    head_y = 0      # 머리의 위치 - 몇열?
    
    # 현재 뱀이 존재하는 칸의 모든 좌표
    snake_queue = deque([(0, 0)])
    
    # 이동 방향 (순서대로 우 -> 하 -> 좌 -> 상)
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    face = 0        # 우회전이면 +1, 좌회전이면 -1
        
    while True:
        curr_time += 1
        
        # 뱀 위치 이동
        nx, ny = head_x + dx[face], head_y + dy[face]
        if nx < 0 or N <= nx or ny < 0 or N <= ny:
            return curr_time    # 벽에 부딪힘 -> 게임 끝!
        if (nx, ny) in snake_queue:
            return curr_time    # 뱀에 부딪힘 -> 게임 끝!
        snake_queue.append((nx, ny))    # 머리의 위치를 큐에 추가
        head_x, head_y = nx, ny
        
        # 사과가 있는 경우
        if (head_x, head_y) in apples:
            apples.remove((head_x, head_y))
        else:
            snake_queue.popleft() # 꼬리의 위치를 큐에서 빼기
                    
        # 시간이 된 경우, 방향을 회전한다
        if comm_queue and comm_queue[0][0] == curr_time:
            command = comm_queue.popleft()[1]
            if command == "L":
                face = (face - 1) % 4
            else:
                face = (face + 1) % 4
                 
print(gameplay()) 

시간 복잡도

• 시간 복잡도를 구하기가 애매한 게, 게임이 끝나는 시점이 정해져 있지 않습니다. 계속 무한반복하다가 벽이나 자기 자신을 쳐 버릴때 끝나는 방식이니까요.
• 일단 그래도 구해 보자면, 게임이 $X$초 소요되고, 사과의 수가 총 $K$개일 때....
  • 매 초마다 if (nx, ny) in snake_queue에서 큐의 원소를 순회
  • 사과의 수가 $K$개이므로 뱀의 길이는 $K+1$까지 길어질 수 있음
  • 즉 순회에는 $O(K)$ 소요
• 최종 $O(X \times K)$

기억할 점

• 데이터의 입출력이 다른 위치에서 발생하는 경우, 큐를 떠올린다.