구현 알고리즘 : 뱀 - 파이썬 (python)

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

3190번: 뱀

 

* 문제 예시 설명

- 뱀은 몸길이를 먼저 늘린 후 이동 → 이동한 칸에 사과가 있다면 꼬리 움직이지 않음

                                                 이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비움

 

- 주어지는 뱀의 방향 변환 정보는 게임 시작 시간으로부터 X초이고, X초가 지난 후에 방향을 변환함

  ex. 8 D, 10 D, 11D, 13L이 주어진 경우

      8초동안 오른쪽으로 진행 (초기 방향 설정이 오른쪽이므로)

      → D (오른쪽으로 방향 회전 : 아래 방향)

      → 2초 동안 아래 방향으로 진행

      → D (오른쪽으로 방향 회전 : 왼쪽 방향)

      → 1초 동안 왼쪽 방향으로 진행

      → D (오른쪽으로 방향 회전 : 위쪽 방향)

      → 2초 동안 위쪽 방향으로 진행 (왼쪽으로 방향 회전 : 왼쪽 방향)

 

- 종료 조건은 벽 또는 자기 자신의 몸과 부딪힐 경우

  → 입력 예시 2와 같이 방향 변환이 끝났는데 자기 자신의 몸과 부딪히지 않은 경우에는

     마지막에 제시한 방향으로 쭉 진행하고 벽에 부딪히면 게임이 종료됨

  ex. 예시 2의 경우 위의 방향 변환 정보를 다 수행하고도 자신의 몸과 부딪히지 않아 게임이 종료되지 않으므로

      최종 방향인 왼쪽 방향으로 계속 진행하고 왼쪽 벽에 부딪히면 게임이 종료됨

 

* 문제 풀이 코드

# 보드의 크기 N
n = int(input())
# 사과의 개수 K
k = int(input())
# 맵 정보
data = [[0] * (n+1) for _ in range(n+1)]
# 방향 회전 정보
info = []

# 맵 정보 (사과가 있는 곳은 1)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로 (동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction


def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보 (꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]

        # 맵 범위 내에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx <= n and 1 <= ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break

        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1

        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1

    return time


print(simulate())

 

 

 

https://github.com/501501/codingTest/blob/master/%EA%B5%AC%ED%98%84/A11.py

GitHub - 501501/codingTest: 이것이 취업을 위한 코딩테스트다 with 파이썬