[Python] 백준 3190번 문제 풀이 - 뱀

문제 링크

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

문제 이해

이 문제는 뱀이 벽에 부딪히거나 자기 자신과 부딪혀서 게임이 끝날 때의 이동 시간을 출력하는 문제입니다.

 

뱀은 처음 0,0에서 시작하고 오른쪽 방향을 바라보고 있습니다.

 

뱀은 매초마다 이동하는데, 몸 길이를 바라보는 방향으로 늘려 머리를 이동시킵니다.

 

이동하는 칸에 사과가 있다면 사과가 없어지고 몸 길이가 1길어지고

 

이동하는 칸에 사과가 없다면 꼬리 부분이 잘려 몸 길이가 그대로인 채로 이동하는 것과 같습니다.

 

방향은 시간 방향 형식으로 주어지는데 특정 시간이 지났을 때 특정 방향(오른쪽 or 왼쪽)으로 회전합니다.

 

방향이 “D”라면 오른쪽으로 회전합니다. 만약 오른쪽이였다면 아래를 바라보게 되고,

 

방향이 “L”이라면 왼쪽으로 회전합니다. 만약 오른쪽이였다면 위를 바라보게 됩니다.

아이디어

우선 저는 칸을 다음과 같이 나누었습니다.

• 그냥 칸 : 0
• 사과가 있는 칸 : 1
• 뱀이 있는 칸 : 2 → 원래 Snake의 “S”로 하려했으나 숫자 배열이기 때문에 비슷한 모양인 2로 했습니다.

우선 while무한루프로 시간이 계속 경과되게 합니다.

 

우선 특정 시간에 뱀이 회전하므로 먼저 특정 시간이 된다면 그 시간에 맞게 방향을 회전합니다.

 

회전 하는 것은 좌하상우 이동배열을 만들어두고 1을 더하고 %4 하는 것과 1을 빼고 %4 하는 것으로 구분했습니다. → (k±1)%4

 

그리고 바라보는 방향으로 이동할 칸을 탐색합니다.

 

만약에 다음 칸이 밖으로 벗어나거나 자기자신(=2)면 while문을 종료합니다.

 

다음 칸에 사과가 있고 없고에서 꼬리를 없앨지 말지가 결정이 되는데요

 

꼬리를 없애는 것은 큐를 사용해서 했습니다.

 

큐에 맨 처음 들어갔던 게 꼬리가 되고 마지막에 들어갔던건 머리가 되게 한다음에

 

사과가 없다면 큐의 맨처음 원소를 없애는 방식으로 꼬리가 없어지는 것을 구현했습니다.

 

처음에는 dfs로 탐색하려다가 2번 예제에서 꼬리가 제대로 없어지지 않을 것이라는 것을 알고 큐로 했습니다.

 

그리고 이동했으면 시간을 1초 늘립니다.

 

이 아이디어를 정리하면 다음과 같습니다.

1. 시간 경과하는 while문을 돌린다.
2. 현재 시간이 방향을 바꾸는 시간이라면 뱀이 바라보는 방향을 바꾼다.
   1. 오른쪽인지 왼쪽인지 따라서 (k±1)%4
3. 다음칸을 확인하고 밖으로 나가거나 자기자신이 나온다면 시간을 1초 늘리고 while문을 탈출한다.
4. 머리를 이동시킨다.
   1. 만약 사과가 있다면 머리를 이동시킨 이후에 꼬리를 자르지 않는다.
   2. 사과가 없다면 머리를 이동시킨 이후에 꼬리를 자른다.
5. 머리 위치를 최신화하고 시간을 1 증가시킨다.

시간복잡도

반복문 내부 연산들의 시간복잡도를 써보면

• 방향 변경 : O(1)
• 다음칸 확인 : O(1)
• 사과 있는지 없는지 확인 후 머리 이동 후 꼬리 자르기 : O(1)
• 머리 위치 확인 후 시간 증가시키기 : O(1)

입니다.

사과가 하나도 없어서 뱀의 길이가 1인채로 계속 무한루프를 돌 수도 있지만 10000초가 지난 이후에는 방향 전환이 일어나지 않기 때문에 최대 10000 X O(1)하고 마지막에 그래프를 탐색하는 것은 많이 이동해봤자 끝까지 이동하는 NXN 맵이기 때문에 최대 N만큼 이동하게 됩니다. 그러면 100정도 이동하고 총 10100 정도의 시간이 걸리기 때문에 10100 X O(1)이기 때문에 가능합니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

from collections import deque

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

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

for _ in range(k):
    y, x = map(int, input().split())
    graph[y-1][x-1] = 1

directions = {}
l = int(input())
for _ in range(l):
    sec, direction = input().split()
    directions[int(sec)] = direction

k = 0
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
queue = deque()

time = 0
y = 0
x = 0
queue.append((y,x))

while True:
    # 방향 결정
    if time in directions:
        if directions[time] == "D":
            k = (k + 1) % 4
        else:
            k = (k-1) % 4

    # 다음 칸
    ny = y + dy[k]
    nx = x + dx[k]
    # 다음 칸이 벗어나거나 2일 경우
    if not ((0<=ny<n) and (0<=nx<n)) or graph[ny][nx] == 2:
        time += 1
        break

    queue.append((ny, nx))
    if graph[ny][nx] == 1:
        graph[ny][nx] = 2  # 머리 이동
    # 사과가 없는 경우
    elif graph[ny][nx] == 0:
        graph[ny][nx] = 2  # 머리 이동
        # 꼬리 제거
        qy, qx = queue.popleft()
        graph[qy][qx] = 0

    # 머리 위치 최신화
    y = ny
    x = nx
    # 횟수 늘리기
    time += 1

print(time)