뱀

📌문제

뱀이 나와서 기어 다니는데 사과를 먹으면 뱀 길이가 늘어나는 게임이 있다. 뱀이 기어다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝납니다.

게임은 NxN 정사각 보드 위에서 진행되고 몇몇 칸에 사과가 놓여졌다. 보드의 상하좌우 끝에는 벽이 있다. 게임을 시작할 때 뱀은 맨 위 좌측에 위치하고 뱀의 길이는 1이다. 뱀은 처음에 오른쪽을 향한다.

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

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

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

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

사과의 위치와 뱀의 이동 경로가 주어질 때 이 게임이 몇 초에 끝날지 계산하시오.

 

📌풀이

2차원 배열 상의 맵에서 뱀이 이동하도록 해야 하므로 2차원 배열상의 특정 위치에서 동, 남, 서, 북 위치로 이동하는 기능 구현

매 시점마다 뱀이 존재하는 위치를 2차원 리스트에 기록

 

📌코드

n = int(input())  # 판 크기
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 and nx <= n and 1 <= ny and 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://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬