BOJ 3190 - 뱀

문제

[백준 온라인 저지 - 3190번](https://www.acmicpc.net/problem/3190)

풀이 과정

뱀 게임을 시뮬레이션해보는 문제입니다.

주의할 점은 N초 후에 회전을 한다는 것이 N+1 초에 회전된 위치로의 이동이 이루어진다는 것입니다.

처음 풀때는 조금 지저분하게 푼 것 같아서 다시 풀어봤습니다.

첫번째 시도

게임판 설정

우선 뱀 게임 시뮬레이션을 위해 (N+2)\*(N+2) 크기의 게임판 board 를 선언하였다.

문제 조건에서 가장자리는 벽으로 하고 게임 시작지점을 1행 1열로 하였으므로 구현의 편의성을 위해 가장자리를 추가한 것이다.

또한 현재 게임판의 상태를 표현해주는 딕셔너리를 사용해서 직관적인 코드 작성을 꾀하였다.

뱀의 이동

가장 까다로운 부분은 뱀의 이동연산입니다.

이를 위해서는 현재 뱀의 위치와 바뀔 회전 방향을 고려해줘야 합니다.

또한 이동시 뱀의 꼬리도 따라와야 하므로 굉장히 복잡한 연산처럼 느껴집니다.

우선 각 방향(동, 서, 남, 북)에 따른 왼쪽과 오른쪽 연산 결과를 처리해줘야 합니다.

현재 방향에 따라 왼쪽과 오른쪽 회전 결과는 다르기 때문에 이를 딕셔너리 자료형에 저장한 뒤 사용하였습니다.

뱀의 이동을 구현하는 여러가지 방법이 있겠지만 나는 매 초마다 회전 연산 목록을 확인해주며

시간이 되었을 때 해당하는 회전 연산이 이루어지도록 하였습니다.

또한 머리와 꼬리의 이동 방향을 각각 따로 유지하면서 회전 연산이 이루어졌을 경우 현재 위치와 다음 이동 방향을 큐에 저장해줬습니다.

어차피 꼬리는 현재 방향을 기준으로 한 칸씩 이동하니까 만약 꼬리가 이전에 한번 꺾인 지점에 도달했을때 이전에 회전했던 방향으로 꼬리도 회전해주도록 하면 되는 것입니다.

코드

첫번째 시도

import sys
from collections import deque


N = int(input())
K = int(input())
apples = []
for _ in range(K):
    apples.append(list(map(int, sys.stdin.readline().split())))
L = int(input())
rotate = []
for _ in range(L):
    line = list(sys.stdin.readline().split())
    rotate.append([int(line[0]), line[1]])


state = {
    'blank': 0,
    'wall': 1,
    'body': 2,
    'apple': 3,
}

# 현재 방향을 고려한 왼쪽과 오른쪽 이동시 다음 방향
next_rotate_dir = {
    'e': {'L': 'n', 'D': 's'},
    'w': {'L': 's', 'D': 'n'},
    's': {'L': 'e', 'D': 'w'},
    'n': {'L': 'w', 'D': 'e'},
}

# 동서남북 이동 좌표
move_pos = {
    'e': [0, 1],
    'w': [0, -1],
    's': [1, 0],
    'n': [-1, 0],
}

def solution():
    timer = 0
    dir = 'e'
    tail_dir = 'e'
    head = [1, 1]
    tail = [1, 1]
    board = [[0 for _ in range(N+2)] for _ in range(N+2)]
    rotate.reverse()

    rotate_log = deque()

    for i in range(N + 2):
        board[0][i] = 1
        board[i][0] = 1
        board[i][N+1] = 1
        board[N+1][i] = 1

    for apple in apples:
        board[apple[0]][apple[1]] = state['apple']

    board[1][1] = state['body']

    while True:
        # 변환 시간이 되면
        if rotate and timer == rotate[-1][0]:
            dir = next_rotate_dir[dir][rotate[-1][1]]
            rotate_log.append((head, dir))  # 변환 지점과 다음 방향을 로그에 저장
            rotate.pop()

        next_head = [head[0] + move_pos[dir][0], head[1] + move_pos[dir][1]]
        head = next_head

        # 자신의 몸 혹은 벽에 머리가 닿으면 종료
        if board[head[0]][head[1]] == state['wall'] or board[head[0]][head[1]] == state['body']:
            timer += 1
            break
        # 사과가 있다면
        elif board[head[0]][head[1]] == state['apple']:
            board[head[0]][head[1]] = state['body']
        # 사과가 없다면
        else:
            board[head[0]][head[1]] = state['body']
            board[tail[0]][tail[1]] = state['blank']

            # 다음 꼬리 위치 찾기
            # 현재 꼬리가 이전에 꺾인 지점이면
            if rotate_log and tail == rotate_log[0][0]:
                tail_dir = rotate_log[0][1]
                rotate_log.popleft()
            next_tail = [tail[0] + move_pos[tail_dir][0], tail[1] + move_pos[tail_dir][1]]
            tail = next_tail
        timer += 1

    return timer


print(solution())

두번째 시도

뱀을 deque 에 저장한 뒤 각 시간마다 머리를 꺼내서 확인하는 방법을 사용했습니다.

또한 각 회전 방향을 딕셔너리로 표현하지 않고 그냥 배열에 선언해줬습니다.

import sys
from collections import deque


N = int(input())
K = int(input())
apples = []
for _ in range(K):
    apples.append(list(map(int, sys.stdin.readline().split())))
L = int(input())
rotate = []
for _ in range(L):
    line = list(sys.stdin.readline().split())
    rotate.append([int(line[0]), line[1]])


state = {
    'blank': 0,
    'wall': 1,
    'body': 2,
    'apple': 3,
}

# 현재 방향을 고려한 왼쪽과 오른쪽 이동시 다음 방향
next_rotate_dir = {
    'e': {'L': 'n', 'D': 's'},
    'w': {'L': 's', 'D': 'n'},
    's': {'L': 'e', 'D': 'w'},
    'n': {'L': 'w', 'D': 'e'},
}

# 동서남북 이동 좌표
move_pos = {
    'e': [0, 1],
    'w': [0, -1],
    's': [1, 0],
    'n': [-1, 0],
}

def solution():
    timer = 0
    dir = 'e'
    tail_dir = 'e'
    head = [1, 1]
    tail = [1, 1]
    board = [[0 for _ in range(N+2)] for _ in range(N+2)]
    rotate.reverse()

    rotate_log = deque()

    for i in range(N + 2):
        board[0][i] = 1
        board[i][0] = 1
        board[i][N+1] = 1
        board[N+1][i] = 1

    for apple in apples:
        board[apple[0]][apple[1]] = state['apple']

    board[1][1] = state['body']

    while True:
        # 변환 시간이 되면
        if rotate and timer == rotate[-1][0]:
            dir = next_rotate_dir[dir][rotate[-1][1]]
            rotate_log.append((head, dir))  # 변환 지점과 다음 방향을 로그에 저장
            rotate.pop()

        next_head = [head[0] + move_pos[dir][0], head[1] + move_pos[dir][1]]
        head = next_head

        # 자신의 몸 혹은 벽에 머리가 닿으면 종료
        if board[head[0]][head[1]] == state['wall'] or board[head[0]][head[1]] == state['body']:
            timer += 1
            break
        # 사과가 있다면
        elif board[head[0]][head[1]] == state['apple']:
            board[head[0]][head[1]] = state['body']
        # 사과가 없다면
        else:
            board[head[0]][head[1]] = state['body']
            board[tail[0]][tail[1]] = state['blank']

            # 다음 꼬리 위치 찾기
            # 현재 꼬리가 이전에 꺾인 지점이면
            if rotate_log and tail == rotate_log[0][0]:
                tail_dir = rotate_log[0][1]
                rotate_log.popleft()
            next_tail = [tail[0] + move_pos[tail_dir][0], tail[1] + move_pos[tail_dir][1]]
            tail = next_tail
        timer += 1

    return timer


print(solution())