[완전탐색, 파이썬] 뱀 4/17

# 뱀 4/17

## 목적: 사과의 위치와 뱀의 이동 경로가 주어질 때 이 게임이 몇 초에 끝나는지 알기

## 맨 위 맨 좌측은 1행 1열이다.

## 벽이나 자기 자신의 몸과 부딪히면 끝난다.

### 못 푼 이유: 문제 이해가 잘 안가는게 사과를 먹었을 때 길이가 늘어난다고 했는데 어떻게 늘어나는 건지 명시되어 있지 않다.
### 몸길이를 늘려 머리를 다음 칸에 위치시킨다는게 길이가 늘어난다는 건가..?

### -> 일단 오해한 점이 있다. 초기 상태는 1,1에서 시작이므로 1,2가 1초 후 위치가 된다. 나는 1,1부터 1초라고 생각을 했다.
### -> 사과를 먹었을 때 사과가 있던 칸 뒤에 꼬리가 생긴다. 그렇게 2칸이 된다. 왜지?


### 해답 핵심 아이디어
### 2차원 배열에서 움직이므로 동,남,서,북의 위치로 이동하는 기능 구현
### 매 시점마다 뱀이 존재하는 위치를 항상 리스트에 기록해야한다.

 

---

 

사과를 먹으면 뱀의 길이가 늘어난다고 한다

-> 사과를 먹으면 길이가 늘어나는 구나

 

벽, 자기 자신의 몸과 부딪히면 게임이 끝난다.

-> 종료 조건이구나, 자기 자신을 코드로 표현하기 위해서 자기 자신의 위치를 담는 자료형이 필요하겠다. 리스트에다가 튜플로 담아두면 좋겠다.

 

게임은 n x n 보드에서 진행되고 사과가 놓여 있습니다.

-> 2차원 배열에 리스트를 만들고 사과는 1로 두고 아닌 것은 0으로 두면 되겠다.

 

게임 시작 시, 맨 위 맨 좌측에 위치하고 뱀의 길이는 1입니다. 뱀은 처음에 오른쪽으로 이동합니다.

-> 초기 시작 상태는 맨 위 맨 좌측에서 시작하는 구나 0행 0열일까 1행 1열일까 -> 밑에 조건까지 읽어보니 1행 1열이구나

 

뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다.

-> 뱀에는 머리와 몸이 따로 있는건가

 

이동한 칸에 사과가 있다면 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다.

-> 뱀에는 머리와 몸이 존재하고 머리가 움직이고 꼬리는 사과가 있으면 움직이지 않는구나

 

이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비워줍니다. 몸길이는 변하지 않습니다.

-> 머리를 먼저 움직여서 확인해보고 사과가 없으면 꼬리가 위치한 칸을 비워주니깐 몸의 길이는 유지를 하네

 

아, 정리를 해보면 뱀은 매초 움직이며 머리를 먼저 움직여서 확인을 하는데

머리를 먼저 움직였을때 벽이거나 자신의 몸통인 경우, 사과가 있는 경우, 사과가 없는 경우로 나뉘는 구나

머리를 먼저 움직였는데 벽이거나 자신의 몸통인 경우 -> 게임 종료 -> 지금까지의 시간을 추가한다.

머리를 먼저 움직였는데 사과인 경우, 꼬리를 그대로 두면 길이가 하나 증가하겠네

머리를 먼저 움직였는데 사과가 아닌 경우, 꼬리를 그대로 두면 안되고 길이가 유지되야하니깐 꼬리부분을 없애야겠다.

 

뱀의 위치정보, 머리에 대한 정보, 꼬리에 대한 정보

지도를 표시할 2차원 리스트

사과x = 0 사과o = 1 뱀 = 2로하자.

이동정보 동서남북, 방향정보

시간은 계속 더해져야하므로 count변수

 

즉 읽으면서 필요한 자료형들을 정리하고 대충 큰 맥락을 정해놓고 바로 코드로 넘어가자.

 

#처음에는 정보를 입력받자.
# 뱀의 위치정보, 머리에 대한 정보, 꼬리에 대한 정보

# 지도를 표시할 2차원 리스트

# 사과x = 0 사과o = 1 뱀 = 2로하자.

# 이동정보 동서남북, 방향정보

# 시간은 계속 더해져야하므로 count변수
def turn(direction, c):
    if c == 'L':
        direction = (direction - 1) % 4
    elif c == 'D':
        direction = (direction + 1) % 4
    return direction

n = int(input()) #size of board
k = int(input()) #number of apples

board = [ [0] * (n + 1) for _ in range(n + 1)] #board information

for i in range(k):
    r,c = map(int,input().split()) #position of apples
    board[r][c] = 1 #apple
    
l = int(input()) #number of directions

direc_info = [] #for directions
for i in range(l):
    x,c = input().split()
    direc_info.append((int(x),c)) #point1.int(x)!!!!

#east south west north
dx = [0,1,0,-1]
dy = [1,0,-1,0]
direction = 0
    
x,y = 1,1 #initial position of head
snake = [(x,y)] #position of snake
board[snake[0][0]][snake[0][1]] = 2
time = 0
index = 0

while True:
    #we have to move snake's head first
    nx = x + dx[direction]
    ny = y + dy[direction]
    
    time += 1
    
    #is it on snake body or wall?
    if 1 <= nx and nx <= n and 1 <= ny and ny <= n and board[nx][ny] != 2:
        #apple?
        if board[nx][ny] == 1:
            x,y = nx,ny
            board[x][y] = 2
            snake.append((x,y))
            #add head's position
        #no apple?
        if board[nx][ny] == 0:
            x,y = nx,ny
            board[x][y] = 2
            snake.append((x,y))
            px,py = snake.pop(0) #point2. 여기서 append는 리스트의 뒤에 더해지고, pop은 뒤에서 뺀다. pop(0)은 앞에서 뺀다. popleft가능
            board[px][py] = 0
            #add head's position and delete tail position
    else:
        break
    
    if index < l and time == direc_info[index][0]:
        direction = turn(direction, direc_info[index][1])
        index += 1
        
print(time)