[Baekjoon] 3190번 : 뱀 (Python, 구현, 큐)

[Baekjoon] 3190번 : 뱀 (Python, 구현, 큐)

 

목차

 

 

 

 

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

3190번: 뱀

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 32484KB / 시간 104ms / 코드 길이 1018B

 

현재 바라보는 방향에 따른 뱀의 이동 그리고 사과를 먹었을 때의 길이 증가를 고려한 코드를 구성해야 한다.

종료 시점 : 벽에 도달했을 때 (x < 0 or y < 0 or x >= n or y >= n) or 내 몸에 닿았을 때(arr[x][y] = 1)

사과를 먹었을 때(arr[x][y] = 2)는 큐에서 popleft를 하지 않지만

방문하지 않았고 사과가 없는 곳(arr[x][y] = 0)에서는 popleft를 통한 표시가 필요하다.

 

활용을 용이하게 하기 위해 2차원 배열을 사용한다.

 

예제 1번을 활용한 표기를 나타내면 다음과 같다.

 

time = 0

 

	0	1	2	3	4	5
0	1(뱀, R)	0	0	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	2(사과)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 1

	0	1	2	3	4	5
0	0	1(뱀, R)	0	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	2(사과)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 2

	0	1	2	3	4	5
0	0	0	1(뱀, R)	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	2(사과)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 3

	0	1	2	3	4	5
0	0	0	0	1(뱀, D)	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	2(사과)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 4

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	1(뱀, D)	2(사과)	0
2	0	0	0	2(사과)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 5

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	1(뱀, D)	2(사과)	0
2	0	0	0	1(뱀, D)	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 6

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	1(뱀, D)	0	0
3	0	0	0	1(뱀, D)	0	0
4	0	0	2(사과)	0	0	0
5	0	0	0	0	0	0

time = 7

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	0	0	0
3	0	0	0	1(뱀, D)	0	0
4	0	0	2(사과)	1(뱀, D)	0	0
5	0	0	0	0	0	0

time = 8

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	2(사과)	0
2	0	0	0	0	0	0
3	0	0	0	0	0	0
4	0	0	2(사과)	1(뱀, D)	0	0
5	0	0	0	1(뱀, D)	0	0

time = 9

벽에 부딪침. 종료

 

from collections import deque

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] = 2

l = int(input())
times = {}
for _ in range(l):
    a, b = input().split()
    times[int(a)] = b

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

# east, south, west, north
dx = [0,1,0,-1]
dy = [1,0,-1,0]

q = deque()
q.append((0,0))
x, y = 0, 0
arr[x][y] = 1
time, current_dir = 0, 0

while 1:
    time += 1
    x, y = x + dx[current_dir], y + dy[current_dir]

    if x < 0 or y < 0 or x >= n or y >= n:
        break

    # eat apple
    if arr[x][y] == 2:
        arr[x][y] = 1
        q.append((x,y))
        if time in times:
            turn(times[time])
    # not visit & not my body
    elif arr[x][y] == 0:
        arr[x][y] = 1
        q.append((x,y))
        tx, ty = q.popleft()
        arr[tx][ty] = 0
        if time in times:
            turn(times[time])
    # touch my body
    else:
        break

print(time)

 

방법 2 - 메모리 32484KB / 시간 100ms / 코드 길이 779B

 

방법 1을 간소화한 버전이다.

 

from collections import deque

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] = 2

l = int(input())
times = {}
for _ in range(l):
    a, b = input().split()
    times[int(a)] = b

# east, south, west, north
dx = [0,1,0,-1]
dy = [1,0,-1,0]

q = deque()
x, y = 0, 0
q.append((x,y))
arr[x][y] = 1
time, d = 0, 0

while 1:
    time += 1
    x, y = x + dx[d], y + dy[d]

    if 0 <= x < n and 0 <= y < n and arr[x][y] != 1:
        if arr[x][y] == 0:
            tx, ty = q.popleft()
            arr[tx][ty] = 0
        arr[x][y] = 1
        q.append((x, y))
    else:
        break

    if time in times:
        if times[time] == 'L':
            d = (d - 1) % 4
        else:
            d = (d + 1) % 4

print(time)