백준 3190번 뱀 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 3190 뱀

문제

3190 뱀

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

3190번: 뱀

삼성 기출문제로 시뮬레이션 문제입니다. 난이도가 조금 있는 문제에 도전해보고 싶어 풀이하게 되었습니다.

https://jjangsungwon.tistory.com/27

위 블로그의 풀이를 참조하였습니다.

---

코드

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())

---

풀이

우리가 아는 길어지는 뱀 게임을 구현하는 문제로 차근차근 풀이해보자면..

우선 인풋 값을 받아야 한다. N, K, arr(게임의 맵을 만든다), K개의 사과를 arr에 1로 표시해준다. 예를 들면

# K = 3 and [[3, 4], [2, 5], [5, 3]]

[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

방향 전환 L번을 딕셔너리 형태로 times로 받고 이는 {3 : 'D', 15 : 'L', 17: 'D'}의 형태로 저장된다.

다음으로 알아야 할 것은 방향 전환에 관한 부분이다.

뱀은 시계 방향 혹은 반시계 방향으로 회전 가능하므로 시계방향 회전을 위쪽 즉 상, 우, 하, 좌로 보고 (0, 1, 2, 3), 반시계 방향일 경우 상, 좌, 하, 우 (0, 3, 2, 1)이 되고 다시 상으로 돌아가는 경우를 위해 % 4로 상으로 다시 돌아가도록 한다.

그리고 dy, dx로 실제 뱀이 좌표를 이동하고 있다면 위로 향하면 (y값만 -1) 오른쪽은 (y = 0, x += 1)와 같은 논리이다.

상, 우, 하, 좌의 인덱스 값을 이용하여 dy, dx를 구한다.

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

이제 마지막으로 실제 뱀을 이동시키며 맵을 벗어나거나 자신의 몸에 닿지 않았을 때에는 사과를 먹거나 아닌 경우를 진행해야 한다. 방향 전환을 해야 할 시간인지 확인 direction 값을 바꿈, 뱀의 머리가 사과가 없는 길을 지나면 꼬리를 0으로 수정, 반대의 경우는 꼬리값 수정하지 않음으로 길이를 표시한다. 

 

난이도가 상당해서 다른 분의 코드를 참조하였고 수정하지 않아도 될 정도로 깔끔하게 잘 정리해 주셔서 조금 더 살을 붙여 정리해보았습니다.

---

풀이 결과

3190 풀이 결과