백준 - 3190번(큐)

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

3190번: 뱀

import sys
from collections import deque
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

arr = [[0 for _ in range(n)] for _ in range(n)] #0으로 채워진 2차원 리스트로 보드 만들기
snake = deque([[0,0]]) #머리 부터 꼬리까지 뱀이 있는 위치들을 표현

case = ['a','b','c','d'] #D와 L에 따라서 방향이 달라지기 때문에 4가지 방향 변화 설정
stat = 'a' #기본 시작은 동쪽으로 1씩 증가
for i in range(k):
    x,y = map(int, sys.stdin.readline().split()) #사과의 좌표
    arr[y-1][x-1] = 1 #사과는 1로 표현

l = int(sys.stdin.readline())
loc = deque([]) #방향 변환 정보 받기 위한 큐

for i in range(l):
    x,c = map(str, sys.stdin.readline().split())
    loc.append([x,c]) # 방향 정보 입력 받기

cnt = 0 #초 count

for _ in range(n**2): #최악의 경우 O(N^2)로 탐색
    if len(loc) > 0: # 방향 전환 정보가 아직 남아 있다면 확인
        if cnt == int(loc[0][0]):
            x = loc.popleft()

            if x[1] == 'D':
                if stat == 'a':#기존 방향 동쪽으로 1씩 증가
                    stat = 'b' #방향 전환후 남쪽으로 1씩 증가

                elif stat == 'b': #기존 방향 남쪽으로 1씩 증가
                    stat = 'c' #방향 전환후 서쪽으로 1씩 증가 == 동쪽으로 1씩 감소

                elif stat == 'c': #기존 방향 서쪽으로 1씩 증가 == 동쪽으로 1씩 감소 
                    stat = 'd' #방향 전환후 북쪽으로 1씩 증가 == 남쪽으로 1씩 감소

                elif stat == 'd': #기존 방향 북쪽으로 1씩 증가 == 남쪽으로 1씩 감소
                    stat = 'a' #방향 전환후 동쪽으로 1씩 증가

            elif x[1] == 'L':
                if stat == 'a': #기존 방향 동쪽으로 1씩 증가
                    stat = 'd' #방향 전환후 북쪽으로 1씩 증가 == 남쪽으로 1씩 감소

                elif stat == 'd': #기존 방향 북쪽으로 1씩 증가 == 남쪽으로 1씩 감소
                    stat = 'c' #방향 전환후 서쪽으로 1씩 증가 == 동쪽으로 1씩 감소

                elif stat == 'c': #기존 방향 서쪽으로 1씩 증가 == 동쪽으로 1씩 감소 
                    stat = 'b' #방향 전환후 남쪽으로 1씩 증가

                elif stat == 'b': #기존 방향 남쪽으로 1씩 증가
                    stat = 'a' #방향 전환후 동쪽으로 1씩 증가

    if stat == 'a':
        if snake[0][0] + 1 > n-1:
            cnt = cnt + 1
            print(cnt)
            break
        else:
            t = [snake[0][0] + 1, snake[0][1]]
            if t in snake: # 머리가 자기 몸통을 만났을때
                cnt = cnt + 1
                print(cnt)
                break
            else:
                snake.appendleft(t)
                if arr[snake[0][0]][snake[0][1]] == 1: #사과 만나면 꼬리 자르지 않음
                    arr[snake[0][0]][snake[0][1]] = 0
                    cnt = cnt + 1
                else:
                    snake.pop() #사과 없으면 꼬리 자름
                    cnt = cnt + 1

    elif stat == 'b':
        if snake[0][1] + 1 > n-1:
            cnt = cnt + 1
            print(cnt)
            break
        else:
            t = [snake[0][0], snake[0][1] + 1]
            if t in snake:
                cnt = cnt + 1
                print(cnt)
                break
            else:
                snake.appendleft(t)
                if arr[snake[0][0]][snake[0][1]] == 1:
                    arr[snake[0][0]][snake[0][1]] = 0
                    cnt = cnt + 1
                else:
                    snake.pop()
                    cnt = cnt + 1

    elif stat == 'c':
        if snake[0][0] - 1 < 0:
            cnt = cnt + 1
            print(cnt)
            break
        else:
            t = [snake[0][0] - 1, snake[0][1]]
            if t in snake:
                cnt = cnt + 1
                print(cnt)
                break
            else:
                snake.appendleft(t)
                if arr[snake[0][0]][snake[0][1]] == 1:
                    arr[snake[0][0]][snake[0][1]] = 0
                    cnt = cnt + 1
                else:
                    snake.pop()
                    cnt = cnt + 1

    elif stat == 'd':
        if snake[0][1] - 1 < 0:
            cnt = cnt + 1
            print(cnt)
            break
        else:
            t = [snake[0][0], snake[0][1] - 1]
            if t in snake:
                cnt = cnt + 1
                print(cnt)
                break
            else:
                snake.appendleft(t)
                if arr[snake[0][0]][snake[0][1]] == 1:
                    arr[snake[0][0]][snake[0][1]] = 0
                    cnt = cnt + 1
                else:
                    snake.pop()
                    cnt = cnt + 1

 

파이썬에서 큐 자료구조를 사용할 일이 있다면 deque()를 사용하는 것이 유리하다.

pop(), popleft(), append(), appendleft()를 모두 사용할 수 있기 때문이다.

이 문제에 큐가 필요한 이유는 뱀이 이동할 때 가장 앞쪽에 조건에 맞게 증감한 수를 넣어주고 가장 마지막에 있는 원소를 버리면 되기 때문이다. 사과(1)를 만난다면 길이가 1 증가하기 때문에 꼬리(snake 큐에 가장 마지막에 있는 원소)를 버릴 필요가 없다.

stat을 바꿔주는 것을 제외한 snake큐에 값이 빠지거나 추가될 때는 무조건 1초가 소요되기 때문에 실행할 때마다 cnt에 1을 증가시켜준다.

머리의 좌표가 본인 몸의 좌표 중 하나 거나 보드의 영역 밖으로 나가면 break 해주고 cnt를 출력해준다.