[백준] 3190 뱀 (Python 파이썬)

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

3190번: 뱀

문제 설명

뱀 꼬리물기 문제이다. 뱀이 사과를 먹으면 점점 꼬리를 늘려가게 되며

뱀의 머리가 꼬리에 닿거나 벽에 닿으면 끝나는 게임이다.

 

뱀의 꼬리를 이동시키는 부분을 큐로 구현하는 부분이 핵심이다.

---

풀이 과정

이 문제는 큐를 이용한 구현 문제로 다음과 같이 접근하였다.

 

① 먼저 그래프(맵)을 모두 0으로 채워준다.

② 사과 위치는 모두 2로 채워준다.

③ 앞으로 뱀이 차지하고 있는 부분은 1로 채워줄 것이다.

④ 뱀이 이동할 때 마다 머리와 꼬리는 한 칸씩 전진한다. (즉, 몸의 길이는 그대로이다.)

⑤ 이동했을 때 사과를 먹으면 머리는 전진하지만 꼬리는 그대로이다. (즉, 몸의 길이가 한 칸 늘어난다.)

⑥ 방향 전환을 해야 하는 타이밍에 맞춰 L이면 왼쪽, D이면 오른쪽으로 방향전환을 한다.

 

이렇게 무엇을 구현해야 할 지를 정리한 후에 이를 하나씩 차례차례 구현해주면 된다.

①②③ 은 그대로 구현을 하면 되기 때문에 따로 설명은 하지 않고

 

④의 경우에는 처음 시작 할 때, [0, 0]을 큐에 넣어 몸길이 1 뱀의 초기 위치 상태를 저장하고,

오른쪽으로 한 칸 이동하여 [0, 0]을 큐에서 pop하고

[0, 1]을 큐에 push하여 뱀의 위치 상태를 변경한다.

 

이런 식으로 뱀을 전진시키면 된다. ( 큐를 뱀의 몸을 나타낸다고 생각하면 된다. )

 

⑤의 경우는 graph[x][y] = 2일 때 이다. 머리만 전진하면 되므로 큐에서 pop을 하지 않고,

큐에 현재 머리 위치만 push함으로써 뱀의 몸 길이를 늘려준다.

 

⑥의 경우에는 현재 시간이 방향전환을 해야 하는 시간이면, 입력한 방향에 맞게 전환을 해주면 된다.

(딕셔너리를 이용해 시간을 키값으로, 방향을 밸류값으로 입력받았다.)

 

이를 코드로 나타내면 다음과 같다.

from collections import deque

n = int(input())
k = int(input())

graph = [[0] * n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for i in range(k):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 2

l = int(input())
dirDict = dict()
queue = deque()
queue.append((0, 0))

for i in range(l):
    x, c = input().split()
    dirDict[int(x)] = c

x, y = 0, 0
graph[x][y] = 1
cnt = 0
direction = 0

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


while True:
    cnt += 1
    x += dx[direction]
    y += dy[direction]

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

    if graph[x][y] == 2:
        graph[x][y] = 1
        queue.append((x, y))
        if cnt in dirDict:
            turn(dirDict[cnt])

    elif graph[x][y] == 0:
        graph[x][y] = 1
        queue.append((x, y))
        tx, ty = queue.popleft()
        graph[tx][ty] = 0
        if cnt in dirDict:
            turn(dirDict[cnt])

    else:
        break

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !