[구현] 뱀 풀이 (백준 3190 / 삼성전자 SW 역량테스트)

3190번: 뱀

 

내 풀이

from collections import deque

n = int(input())
arr = [[0] * n for _ in range(n)]
k = int(input())
for _ in range(k):
    x, y = map(int, input().split())
    arr[x - 1][y - 1] = 1
l = int(input())
action = deque()
for _ in range(l):
    x, c = input().split()
    action.append((int(x), c))

def rotate(d, act_d): # "UP", "RIGHT", "DOWN", "LEFT" 0 1 2 3
    return (d + 1) % 4 if act_d == "D" else (d + 3) % 4

def move(hq, tq, dx, dy):
    hx, hy = hq.popleft()
    if hx + dx >= n or hx + dx < 0 or hy + dy >= n or hy + dy < 0: # 맵 바깥이라면
        return False
    hq.append((hx + dx, hy + dy))
    tq.append((hx, hy))
    if arr[hx + dx][hy + dy] == 7:  # 자신이라면
        return False
    elif arr[hx + dx][hy + dy] == 1:  # 사과라면
        pass
    else:
        tx, ty = tq.popleft()
        arr[tx][ty] = 0

    arr[hx + dx][hy + dy] = 7
    return True

def start(arr):
    hq, tq = deque(), deque() # 머리 큐, 꼬리 큐
    hq.append((0, 0))
    d, t = 1, 0 # 시작 방향, 시작 시간
    arr[0][0] = 7 # 뱀 시작 위치
    act_clear, act_time, act_d = True, None, None # 액션 가능, 시간, 회전방향

    while True:
        t += 1
        if d == 0: # 위쪽
            if not move(hq, tq, -1, 0): # 움직일 때 조건에 걸린다면 종료
                return t
        elif d == 1: # 오른쪽
            if not move(hq, tq, 0, 1):
                return t
        elif d == 2: # 아래쪽
            if not move(hq, tq, 1, 0):
                return t
        elif d == 3: # 왼쪽
            if not move(hq, tq, 0, -1):
                return t
        if action and act_clear: # 액션이 존재하고 꺼낼 수 있는 상황이면
            act_time, act_d = action.popleft()
            act_clear = False
        if t == act_time:
            d = rotate(d, act_d)
            act_clear = True

print(start(arr))

접근한 방식

사과는 1, 뱀은 7로 표현했다. 단순하게 인덱스를 늘려주는 방식으로 생각하다 뱀이 방향을 틀어 꺾이는 부분에서 문제가 발생한다는 것을 알았고, 2개의 큐(머리 큐 hq, 꼬리 큐 tq)를 사용하는 것으로 문제를 해결했다.

 

move 함수에서 hq에서 먼저 위치를 빼서 tq에 넣어주고 머리가 이동할 위치를 hq에 넣어준다. 뱀의 머리가 이동한 위치가 빈 곳(0)이라면 꼬리 부분을 한칸 자르기 위해 tq에서 하나를 제거해주고, 이동한 위치가 사과(1)라면 꼬리 부분을 제거할 필요가 없다. 그러면 뱀의 길이는 늘어나게 된다. 

 

현재의 방향에 대하여 move를 수행하고 움직일 수 없는 상황(False)일때, 그때의 타임(t)를 반환하면 정답 판정을 받을 수 있다.