[ 백준 3190 ] 뱀 - Python

문제 보기

이 문제는 시뮬레이션 문제이다.

 

삼성 기출문제는 대부분 bfs로 풀거나 지도에서 움직이는 형태가 많은 것 같다. 이 문제 또한 지도에서 움직이는 형태이다.

 

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

- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.

- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.

- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

 

문제에서 요구하는 사항을 하나씩 완성시키면 쉽게 구현할 수 있다.

 

알고리즘 수행 과정은 아래와 같다.

1. 2차원 배열(N x N)을 만든다. (0으로 초기화)

2. 사과의 위치에 1을 저장한다.

3. (0, 0)에서 뱀은 시작하며 뱀이 지나갔던 곳은 2로 저장한다.

- 방향의 변화가 생겼는지 확인한다.

- 뱀의 머리가 사과가 없는 위치로 가면 꼬리의 값을 0으로 수정한다. (2 -> 0)

- 뱀의 머리가 사과가 있는 위치로 가면 꼬리의 값을 수정하지 않는다.

4. 3번의 과정을 벽에 부딪히거나, 자기 자신의 몸에 부딪힐 때까지 진행한다.

 

코드

from collections import deque


def change(d, 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
    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
            visited.append([y, x])
            if time in times.keys():
                direction = change(direction, times[time])
            time += 1
        else:  # 본인 몸에 부딪히거나, 벽에 부딪힌 경우
            return time


if __name__ == "__main__":

    # input
    N = int(input())
    K = int(input())
    arr = [[0] * N for _ in range(N)]
    for _ in range(K):
        a, b = map(int, input().split())
        arr[a - 1][b - 1] = 1  # 사과 저장
    L = int(input())
    times = {}
    for i in range(L):
        X, C = input().split()
        times[int(X)] = C
    print(start())