[백준] 3190 뱀 python

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

3190번: 뱀

# import sys; input = sys.stdin.readline
from collections import deque
N = int(input())
K = int(input())
apples = set([tuple(map(int, input().split())) for _ in range(K)])
L = int(input())
change = [input().split() for _ in range(L)]
change_i = 0

_map = []
for i in range(N + 2):
    if i == 0 or i == N + 1:
        _map.append([-1 for _ in range(N + 2)])
    else:
        _map.append([-1] + [0 for _ in range(N)] + [-1])
# print(*_map, sep='\n')
# print(apples, change)
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
dir_i = 0 # 0,1,2,3 => r,d,l,u
pos_q = deque()
pos_q.append((1, 1))
time = 0
while True:
    time += 1
    # print(dir_i, time)
    r = pos_q[-1][0] + dr[dir_i]
    c = pos_q[-1][1] + dc[dir_i]
    tmp_pos_q = (r, c)

    # move
    if _map[r][c] == -1: # 벽에 닿는 경우
        break
    # tail = pos_q.popleft() # 꼬리를 물어도 진행하는 경우 주석 해제
    if tmp_pos_q in apples:
        # pos_q.appendleft(tail) # 꼬리를 물어도 진행하는 경우 주석 해제
        pos_q.append(tmp_pos_q)
        apples.remove(tmp_pos_q)
    elif tmp_pos_q in pos_q:
        break
    else:
        pos_q.popleft() # 꼬리를 물어도 진행하는 경우 주석 처리
        pos_q.append(tmp_pos_q)

    # change direction
    if change_i < len(change) and str(time) == change[change_i][0]:
        if change[change_i][1] == 'L':
            dir_i = (dir_i - 1) % 4
        else: # change[change_i][0] == 'D':
            dir_i = (dir_i + 1) % 4
        change_i += 1
print(time)

삼성 A형 기출문제이고 구현 문제이다. 딱 삼성 냄새가 나는 문제이다. 

문제에서 주어진 규칙 대로 구현하면 된다. 조금더 쉽게 처리하기 위해 가상의 벽을 만들어서 닿으면 끝나도록 해두었고 사과의 위치는 set 자료구조를 사용해서 먹었을때 판별을 쉽게 하였다. 뱀의 위치를 계산할 땐 큐를 사용하였다. (deque 사용)

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

이 문제에서 조금 눈여겨 봐야할 것은 세 번째 예제이다. 꼬리가 닿을때 어떻게 판별해야할지 알려주기 때문이다. 아래 그림(1번 head, 6번 tail, 진행방향은 위쪽)과 같이 머리가 꼬리에 있는 자리로 옮기는 경우, 충돌로 해서 반복문을 탈출할지 아니면 진행할지 판별할 수 있다. 

이 상황에서 어떻게 해야할까?

세번째 예제에서 13초에서 뱀의 위치는 [(1, 8), (1, 9), (2, 9), (3, 9), (3, 8), (2, 8)] 이다. (1, 8)이 꼬리이고 (2, 8) 이 머리인데 진행방향이 위쪽이므로 진행방향과 꼬리가 겹친다. 진행한다고 하면 세번째 예제도 두번째 예제와 같이 21이 나오므로 진행할수 없게 만들어야한다. 

---

골드 5짜리 구현문제는 그렇게 어렵진 않은거같다. 같은 난이도의 dp나 dfs가 더 어려운듯...