boj

백준 3190 뱀 -python

boj-3190

Posted by 동식이 블로그 on November 12, 2019

백준 3190 뱀 -python

문제

  • 시뮬레이션 문제


문제풀이

  • 현재 방향에 따라, 주어지는 입력 D, L에 따라서 움직임을 다르게 주기
  • 가장 중요한 것은 뱀이 사과를 먹었을 때와 안먹었을 때의 구분
    • 사과를 먹었을 때
      • 사과를 삭제하고 꼬리는 늘어난 채 유지
    • 사과를 먹지 못했을 때
      • 꼬리를 하나 줄여줌, 몸길이의 변화가 없다
    • 이를 위해서 뱀의 꼬리부터 머리까지의 정보를 가지고 있는 queue를 만들어서 표시


code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
dx = [0,1,0,-1]
dy = [1,0,-1,0]

def change(d, c):
    if(c == "L"):
        d = (d-1)%4
    else:
        d = (d+1)%4
    return d
        
def start():
    cnt = 0
    # 뱀 위치 표시
    x = 0
    y = 0
    arr[x][y] = 3
    d = 0
    idx = 0
    # 뱀의 꼬리 ~ 머리까지의 정보를 q에 담기
    q = []
    q.append((x,y))
    while(True):
        # 몇초에 방향 전환 하는지
        if(game[idx][0] == cnt):
            d = change(d, game[idx][1])
            idx += 1
        nx = x + dx[d]
        ny = y + dy[d]
        # 범위안에 있고, 자기자신이 아니라면
        if(0<=nx<n and 0<=ny<n and arr[nx][ny] != 3):
            # 사과를 먹으면 꼬리는 그대로
            if(arr[nx][ny] == 1):
                arr[nx][ny] = 3
                q.append((nx,ny))
            # 사과를 못먹으면 꼬리 하나 떼기
            elif(arr[nx][ny] == 0):
                arr[nx][ny] = 3
                q.append((nx,ny))
                tx, ty = q.pop(0)
                arr[tx][ty] = 0
            x = nx
            y = ny
            cnt += 1
        else:
            cnt += 1
            break
    return cnt

n = int(input())
k = int(input())
arr = [[0]*n for _ in range(n)]
for _ in range(k):
    a, b = map(int, input().split())
    arr[a-1][b-1] = 1
l = int(input())
game = [[0,0]]*10000
for i in range(l):
    x, c = input().split()
    game[i] = [int(x), c]
res = start()
print(res)