백준 3190 : 뱀

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

3190번: 뱀

 

해결 방법 : Linked List

• board가 (2 <= N <= 100)이고 최대 second가 10,000밖에 되지 않기 때문에 최대 10,100초 안에 답이 나온다. 따라서 1초 마다 뱀이 움직이는 것을 그대로 구현하였다.
• 뱀은 연결 리스트로 표현된다. 현재 sec에 이동한 칸은 리스트의 head에, 꼬리의 끝은 리스트의 tail이 될 것이다.
• 사과를 먹으면 해당 sec에는 tail을 감소시키지 않는다.
• 방향 전환은 시간은 순서대로 있으므로 방향 전환 정보를 담은 배열의 0번째만 참조한다.
• board 범위를 벗어나거나, 뱀을 표현한 연결 리스트안에 있는 좌표쌍에 들어가게 되면 종료. 

 

import sys
input = sys.stdin.readline
from collections import deque

def solution(N, apples, rotates):
    D = {(0,1) : ((1,0),(-1,0)), (1,0) : ((0,-1),(0,1)),
         (0,-1) : ((-1,0),(1,0)), (-1,0) : ((0,1),(0,-1))} # 방향 전환 
    Q = deque([(0,0)]) # linked list로 사용
    sec, d = 0, (0,1) # 처음 시작, 처음 방향(Right)
    while True:
        sec += 1
        r, c = Q[-1][0] + d[0], Q[-1][1] + d[1] # 이동한 좌표 row, col
        
        if not (0 <= r < N and 0 <= c < N) or (r, c) in Q: # board 이탈 or 몸통박치기
            return sec
        
        Q.append((r, c)) # 머리 추가

        if (r+1, c+1) not in apples: # 꼬리 제거
            Q.popleft()
        else:
            apples.remove((r+1, c+1)) # 먹은 사과 제거
        
        if rotates: # 방향 전환
            if rotates[0][0] == str(sec):
                d = D[d][0] if rotates.pop(0)[1] == 'D' else D[d][1]


if __name__ == '__main__':
    N = int(input())
    K = int(input())
    apples = [tuple(map(int, input().split())) for _ in range(K)]
    L = int(input())
    rotates = [tuple(input().split()) for _ in range(L)]
    result = solution(N, apples, rotates)
    print(result)