[백준] 3190번, 뱀 (Python)

문제

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

3190번: 뱀

 

코드

import collections
n = int(input())
k = int(input())

graph = [[0]*(n+1) for _ in range(n+1)]

for i in range(k):
    x,y = map(int, input().split())
    graph[x][y] = 2 # 사과는 2로 초기화

l = int(input())
direction = []
for i in range(l):
    x,y = input().split()
    direction.append([int(x),y])

direction.sort()

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

def simulation(x,y):
    d = 0 # 방향
    graph[x][y] = 1 # 시작위치는 1로 초기화
    queue = collections.deque()
    queue.append((x,y))
    time = 0
    
    while queue:
        time += 1
        x += dx[d]
        y += dy[d]
        if 1 <= x < n+1 and 1 <= y < n+1 and graph[x][y] != 1:
            if graph[x][y] == 2:
                graph[x][y] = 1
            elif graph[x][y] == 0:
                nx,ny = queue.popleft() # 꼬리에 위치
                graph[x][y] = 1
                graph[nx][ny] = 0
            queue.append((x,y))
        else:
            return time
        
        if direction:
            if time == int(direction[0][0]):
                if direction[0][1] == 'D':
                    d = (d+1) % 4
                else:
                    d = (d-1) % 4
                direction.pop(0)
print(simulation(1,1))

1,1 좌표부터 시작하니까 계산하기 편하게 graph를 n+1 범위로 만들어준다.

사과는 grpah에 2로 표시, 뱀에 위치는 1로표시 빈칸은 0으로 표시하였다.

 

시뮬레이션 함수를 돌아주는데 범위를 벗어나거나 뱀 자기 자신을 만나면 종료한다.

이동한 칸이 사과일 경우는 꼬리를 움직일 필요없고

이동한 칸이 빈칸일 경우만 queue(이동하기 전 뱀에 위치 저장한 곳) 에서 값을 꺼내 0으로 바꿔준다.

 

direction을 오름차순으로 정렬해줘 순서대로 나올수 있게 만들어준다.

time이랑 direction[0][0](정렬 했으므로 가장 작은 시간)이 같다면 방향전환을 해준후 direction에서 pop해준다.

 

함수가 종료될때까지 계속 반복한다.