[큐, 시뮬레이션] 백준 3190번 뱀 with Python3 ★

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

3190번: 뱀

문제

정답 풀이

from collections import deque


def change(d, c):  # d는 현재 direction 값, c는 현재 시간에 맞는 방향전환 지시
    # 상(0) 우(1) 하(2) 좌(3)
    # 동쪽 회전: 상(0) -> 우(1) -> 하(2) -> 좌(3) -> 상(0) : +1 방향
    # 왼쪽 회전: 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0) : -1 방향
    if c == "L":
        d = (d-1) % 4
    else:
        d = (d+1) % 4
    return d


# 상 우 하 좌
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]


def start():
    direction = 1  # 초기방향
    time = 1   # 시간
    y, x = 0, 0  # 초기 뱀위치
    visited = deque([[y, x]])  # 방문 위치 / 지나갈 경우 해당 위치를 반환해서 방문 기록을 지우기 위함.
    arr[y][x] = 2  # 아마 2차원 배열상 자기 몸 위치 기록

    while True:

        y, x = y + dy[direction], x + dx[direction]

        if 0 <= y < N and 0 <= x < N and arr[y][x] != 2:
            # 벽을 만나지 않았거나, 자기 몸이 있는 곳이지 않을경우

            if not arr[y][x] == 1:  # 사과가 없는경우
                temp_y, temp_x = visited.popleft()  # 큐처럼 뒤에 넣고 앞부터 뺸다.
                arr[temp_y][temp_x] = 0  # 꼬리 제거.

            arr[y][x] = 2  # while문이 시작 될 때 y,x가 업데이트됬고
            # y,x는 현재 이동한 머리 위치이기에 2로 바꿔줌.
            # 2는 2차원 배열상 내 몸위치임을 알 수 있다.

            visited.append([y, x])  # 다시 방문 위치를 임시 저장

            if time in times.keys():
                # .keys()는 times라는 딕셔너리의 key 값들을 가져온다.
                # times의 key 값은 시간임으로, 현재 time과 같은 key가 있을경우
                # direction을 chagne() 함수를 통해 바꿔준다.

                # d는 현재 direction 값, c는 현재 시간에 맞는 방향전환 지시
                direction = change(direction, times[time])

            time += 1  # 모든 행동이 끝나면 시간 기록을 한다.

        else:  # 본인 몸에 부딪히거나, 벽에 부딪힌 경우
            return time


if __name__ == "__main__":

    # input
    N = int(input())
    K = int(input())
    # 2차원 배열 N*N 0으로 초기화
    arr = [[0] * N for _ in range(N)]

    for _ in range(K):
        a, b = map(int, input().split())
        # 주어지는 좌표값은 1부터 시작하기에 a-1행, b-1열에 업데이트
        arr[a-1][b-1] = 1  # 사과 저장

    # 방향전환 정보
    L = int(input())
    times = {}  # 딕셔너리형

    for i in range(L):
        X, C = input().split()  # X 시간, C 방향전황 방향 L:왼, D: 오
        times[int(X)] = C
        #eg:{3: 'D', 15: 'L', 17: 'D'}

    print(start())

출처:https://jjangsungwon.tistory.com/27

 

해석

말은 쉬운 그냥 주어진 대로 행동 할 수 있는 구현문제다.

 

도전해볼 만 했던것 같은데 너무 답을 빨리 봐버린거 같다.

 

큐 개념은 visited에 사용된다.