프로그래밍으로 뱀을 만드는 방법? -뱀-

1. 문제

 

3190번: 뱀 (acmicpc.net)

3190번: 뱀

 

규칙에 따라 움직이는 뱀의 이동경로가 주어질때, 언제 게임이 끝나는지 구하는 프로그램을 작성

 

 

2. 풀이

 

뱀이 이동할때, 먼저 머리를 다음 칸에 위치시키고

 

사과가 있으면 사과를 먹고 그대로 두거나

 

사과가 없으면 꼬리가 위치한 칸을 비우므로

 

deque를 이용해서 뱀의 자취를 표현할 수 있을 것 같다

 

꼬리를 비울때는 deque의 0번째 원소를 제거하고, 머리를 넣을때는 deque의 마지막 원소를 넣어주고

 

--------------------------------------------------------------------------------------------------------------------------------------

 

입력을 먼저 받는다, 사과 위치가 행,열로 주어지므로 평소에 좌표를 x,y로 쓴다면 y,x로 바꿔줘야한다

 

0,0부터 쓰는지, 1,1부터 쓰는지에 따라 좌표도 어떻게 주어지는지 주의해서 봐야한다

 

이 경우 1,1부터 쓰므로 y-1,x-1로 표시해줘야

 

from collections import deque
from sys import stdin

#보드 크기
n = int(stdin.readline())

#사과 개수
k = int(stdin.readline())

maps = [[0]*n for _ in range(n)]

for _ in range(k):
    
    #사과 위치는 행,열
    y,x = map(int,stdin.readline().split())

    maps[y-1][x-1] = 1 #사과를 배치
    
#방향전환 리스트
dir_list = deque()

for _ in range(L):
    
    x,c = stdin.readline().rstrip().split()

    dir_list.append((int(x),c)) #증가하는 순서대로 주어진다

 

특히 방향전환 정보도 증가하는 순서대로 주어진다는 점이 문제에 나와있으므로 따로 정렬하거나 할 필요는 없다

 

문제에서 방향전환도 한다고 나와있으므로, 방향전환 사전을 따로 정의해서 만든다

 

#우, 좌 , 하, 상
delta = [[1,0],[-1,0],[0,1],[0,-1]]

#방향전환 사전

change_dir = {0:{'L':3, 'D':2}, 1:{'L':2, 'D':3}, 2:{'L':0, 'D': 1}, 3:{'L':1,'D':0}}

 

뱀이 움직이다가 자기 자신의 몸과 부딪혀도 게임이 끝나므로, visited 배열을 만들어서 현재 어디에 뱀의 몸이 존재하는지도 나타내준다

 

#뱀의 자취를 deque에 순서대로 담는다
#0번이 뱀의 꼬리
#-1번이 뱀의 머리
snake = deque([(0,0,0)])

visited = [[0]*n for _ in range(n)]

visited[0][0] = 1 #최초 맨 좌측에 위치

 

그래서 뱀은 움직이다가, 1이 표시된 visited 지역에 움직여야한다면, 게임이 끝날 것이다

 

모든 준비가 끝나면, 문제 시뮬레이션 순서대로 성실하게 구현

 

#시뮬레이션
t = 1 #시작시간

while 1:
    
    x,y,d = snake.pop()

    #머리를 다음칸에 위치시킨다

    dx = x + delta[d][0]
    dy = y + delta[d][1]

 

현재 뱀의 -1번째 원소는 뱀의 머리이므로, 이것을 빼서 방향에 따라 다음칸에 위치시킨다

 

그 좌표가 dx,dy이다.

 

그러면 pop시킨 x,y는 뱀의 몸통이 되므로, 이것을 다시 deque에 넣어주자..

 

매우 사소한 디테일이라 이것을 생각하기 쉽지 않을 수 있다

 

    #x,y,d는 꼬리(몸통)가 되니까 다시 꼬리(몸통)는 deque에 넣어주고
    snake.append((x,y,d))

 

움직였는데 배열의 범위를 벗어나지 않는 경우와 배열의 범위를 벗어나는 경우가 존재할 것이다

 

배열의 범위를 벗어나 벽에 부딪힐려고 한다면 게임이 끝난다

 

    if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1: #배열의 범위를 벗어나지 않는 경우,
    
    
    else: #배열의 범위를 벗어나는 경우
        
        break #게임 끝

 

 

배열의 범위를 벗어나지 않는 경우, 만약에 visited 배열을 검사해서 이미 표시된 지역에 머리를 옮겨야하는 경우?

 

자기 자신의 몸과 부딪히는 경우이다.

 

    if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1: #배열의 범위를 벗어나지 않는 경우,
        
        if visited[dy][dx] == 1: #자기 자신의 몸과 부딪힌다면?

            break #게임 종료

 

방문하지 않은 지역을 방문하는 경우..

 

사과가 있냐 없냐에 따라 달라진다

 

사과가 있다면 사과를 먹고, maps의 값을 0으로 바꿔준다.

 

사과가 존재하지 않는다면? 뱀의 꼬리를 제거하고

 

visited에서 해당 꼬리의 좌표에 대응하는 값을 0으로 바꿔주면 꼬리를 제거하는 것

 

        else: #자기 자신의 몸과 부딪히지 않는다면...
            
            visited[dy][dx] = 1

            if maps[dy][dx] == 1: #맵에 사과가 존재한다면...
                
                maps[dy][dx] = 0 #사과 먹고

            else: #사과가 존재하지 않는다면...
                
                t_a,t_b,tail_d = snake.popleft() #꼬리를 한칸 줄이고

                visited[t_b][t_a] = 0 #꼬리를 줄였으니, 자취에서 제거

 

뱀의 머리를 deque에 넣기전에 방향전환을 하게 되는지 검사해야한다

 

    #방향 전환 여부
    turn = False

    for i in range(L): 
        
        if dir_list[i][0] == t: #방향전환 시간이 현재 시간과 일치하는 경우를 만나면..
            
            d = change_dir[d][dir_list[i][1]]
            turn = True
            break
    
    if turn:
        
        dir_list.popleft() #증가하는 시간 순이므로, 최초 turn을 하면, 사용한 원소이므로 제거
        L-=1 #원소 1개 감소했으므로

 

방향전환 리스트 dir_list에 들어있는 원소의 개수는 L개

 

증가하는 순서대로 들어가있으므로, 0~L-1까지 순회해서, 최초로 현재 시간 t와 같은 시간을 만나게 된다면...

 

방향전환 사전 change_dir에 정의한대로 방향 d값을 바꿔주고

 

증가하는 순서대로 들어가있기 때문에 dir_list에서 0번째 원소를 제거해주면 된다.

 

그리고 원소 1개 감소했으니 길이 L도 1을 감소시키고

 

다음에 (dx,dy,d)를 뱀의 머리인 -1번 원소에 넣어주고 다음 시간으로 이동시켜서 반복을 계속하면 끝

 

from collections import deque
from sys import stdin

#보드 크기
n = int(stdin.readline())

#사과 개수
k = int(stdin.readline())

maps = [[0]*n for _ in range(n)]

for _ in range(k):
    
    #사과 위치는 행,열
    y,x = map(int,stdin.readline().split())

    maps[y-1][x-1] = 1 #사과를 배치

L = int(stdin.readline())

#방향전환 리스트
dir_list = deque()

for _ in range(L):
    
    x,c = stdin.readline().rstrip().split()

    dir_list.append((int(x),c)) #증가하는 순서대로 주어진다

#뱀의 자취를 deque에 순서대로 담는다
#0번이 뱀의 꼬리
#-1번이 뱀의 머리
snake = deque([(0,0,0)])

#우, 좌 , 하, 상
delta = [[1,0],[-1,0],[0,1],[0,-1]]

#방향전환 사전

change_dir = {0:{'L':3, 'D':2}, 1:{'L':2, 'D':3}, 2:{'L':0, 'D': 1}, 3:{'L':1,'D':0}}

visited = [[0]*n for _ in range(n)]

visited[0][0] = 1 #최초 맨 좌측에 위치

#시뮬레이션
t = 1 #시작시간

while 1:
    
    x,y,d = snake.pop()

    #머리를 다음칸에 위치시킨다

    dx = x + delta[d][0]
    dy = y + delta[d][1]

    #x,y,d는 꼬리(몸통)가 되니까 다시 꼬리(몸통)는 deque에 넣어주고
    snake.append((x,y,d))

    if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1: #배열의 범위를 벗어나지 않는 경우,
        
        if visited[dy][dx] == 1: #자기 자신의 몸과 부딪힌다면?

            break #게임 종료
        
        else: #자기 자신의 몸과 부딪히지 않는다면...
            
            visited[dy][dx] = 1

            if maps[dy][dx] == 1: #맵에 사과가 존재한다면...
                
                maps[dy][dx] = 0 #사과 먹고

            else: #사과가 존재하지 않는다면...
                
                t_a,t_b,tail_d = snake.popleft() #꼬리를 한칸 줄이고

                visited[t_b][t_a] = 0 #꼬리를 줄였으니, 자취에서 제거
    
    else: #배열의 범위를 벗어나는 경우
        
        break #게임 끝

    
    #방향 전환 여부
    turn = False

    for i in range(L): 
        
        if dir_list[i][0] == t: #방향전환 시간이 현재 시간과 일치하는 경우를 만나면..
            
            d = change_dir[d][dir_list[i][1]]
            turn = True
            break
    
    if turn:
        
        dir_list.popleft() #증가하는 시간 순이므로, 최초 turn을 하면, 사용한 원소이므로 제거
        L-=1 #원소 1개 감소했으므로
    

    snake.append((dx,dy,d)) #머리를 넣어주고

    t += 1 #다음 시간으로 이동


print(t)