[백준] 3190번: 뱀

https://www.acmicpc.net/problem/3190

initial

This is a samsung question and I thought so.

my initial thinking was storing the body position in a list or some kind of DS and updating the body position whenever we move. But I wasnt sure how to deal with when we changed direction like that second pic.

I almost got the changing direction bit correect, except instead of using dictionary to store that directions, we should use a list to prevent keyError because if we have negative values for key in dic (when we go left beyond 0), then list won't cause Error. But even list will cause 'list index out of range error' when we go like -4 so we modulo it by 4 when we change direction.

solution

So we indeed store our snake body position in a DS but what doe we use? We use a queue!

https://hongcoding.tistory.com/127
very well explained here

Then the most difficult bit, how do we implement the changing direction part and eating apple and just moving when there is no apple?

from collections import deque

n = int(input())
m=int(input())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b]=2
k = int(input())
dicMove = dict()
for _ in range(k):
    x,c = input().split()
    dicMove[int(x)] = c

moves = [[0,1],[1,0],[0,-1],[-1,0]]
queue =deque()
queue.append((1,1))
ans = 0
x,y=1,1
graph[x][y]=1
direction=0

def turn(alpha):
    global direction
    if alpha=='L':
        direction = (direction-1)%4
    else:
        direction = (direction+1)%4

while True:
    ans+=1
    x+=moves[direction][0]
    y+=moves[direction][1]
    if 0<x<=n and 0<y<=n:
        if graph[x][y]==2:
            queue.append((x,y))
            graph[x][y]=1
            # tail_x, tail_y = queue.popleft()
            # graph[x][y]=0
            if ans in dicMove:
                turn(dicMove[ans])
        elif graph[x][y]==0:
            graph[x][y]=1
            queue.append((x,y))
            tail_x, tail_y = queue.popleft()
            graph[tail_x][tail_y]=0

            if ans in dicMove:
                turn(dicMove[ans])
        else:
            break
    else:
        break
print(ans)

1) for changing direction, we store our future movements and when they are gonna happen in a dicMove dictionary. If the next time is in our dicMove dictionary, we change direction and the x,y will be incremented by the updated direction instead of the old direction

2) when there is applie (graph[x][y] will be 2), then we append the extended head to the back of the queue. Very important that it is at the back!!. My initial thinking was always to put it at the front but nope. And we mark the x and y as 1 (visited)

[wrong explanation]And whether there is apple or not, the tail needs to be popped. So we popleft our queue, which contains our tail and mark graph[tail_x][tail_y] back to 0 as unvisited.

[fxied]actually if there is apple, we shouldnt pop cuz then our body length will be +1 -1 which will be 0 constant. We need to extend our body length so dont pop

3) when no apple, we again append the new x,y (head) to the back of the queue. But here we need to pop the tail by popleft and mark the tail grid as unvisited (0) again.

4) when graph[x][y]==1, that means we are visiting an already visited grid, which is our own snake body so we break out of loop.

5) after each traversal, we check if we need to turn direction and update direction value accordingly.

important bit is that the way we are implementing this queue and update direction, even when we turn multiple times, since we are updating and incrementing x and y with new direction and appending it to the back of the queue whilst popping the tail, it deals with the difficult turning logic.

complexity

The given code appears to be a Python program that simulates the movement of a snake in a grid. The goal is to find the time it takes for the snake to go out of bounds or collide with itself. Let's analyze the time complexity of this code:

1. Input Processing: Reading the input values has a constant time complexity of O(1) because the number of inputs (n, m, k) is not dependent on the size of the grid.

2. Grid Initialization: Creating a 2D grid of size (n+1) x (n+1) and initializing it with zeros has a time complexity of O(n^2). This is a one-time operation.

3. Storing Obstacles: Looping through m obstacles and updating the grid accordingly has a time complexity of O(m), where m is the number of obstacles.

4. Simulating Snake Movement: The main part of the code simulates the movement of the snake. It uses a queue to keep track of the snake's body positions and iterates through the grid. The key operations are as follows:

   • A while loop that continues until the snake goes out of bounds or collides with itself. The number of iterations depends on the snake's movement.
   • In each iteration, the code updates the snake's position, checks if it hits a wall or itself, and makes decisions based on the dicMove dictionary.
   • The turn function updates the direction of the snake, and its time complexity is O(1).

5. Queue Operations: Enqueuing and dequeuing positions in the queue has a constant time complexity of O(1) per operation.

In this code, the dominant factor for the time complexity is the snake's movement simulation. The number of iterations in the while loop is determined by the snake's movement and the dicMove dictionary. In the worst case, the snake could traverse the entire grid (or at least a large portion of it) without colliding or going out of bounds. Therefore, the time complexity of this code depends on the snake's movement, and it's challenging to provide a precise time complexity without knowing the specific movement pattern and grid size. However, in most cases, it will be limited by the size of the grid, so it could be considered O(n^2) in practice.