[BaekJoon] 백준 3190번 뱀

[BaekJoon] 백준 3190번 뱀

 

문제: www.acmicpc.net/problem/3190

 

내코드

 

- 그대로 구현하기만 하면 되는 간단한 문제였다.

- 처음에는 내용 이해를 하고 어떻게 구현해야 할지 막막했는데 하나씩 짜다보면 풀리는 문제였다.

- 뱀의 몸이 있는 위치를 deque에 넣어주고 빼줘서 뱀이 이동하는 것을 나타냈다.

- 포인트는 문제에 적혀있는 이 세문장이라고 생각한다. 이 순서대로 코드를 작성하였다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

- 또 까다로웠던 부분은 왼쪽, 오른쪽으로 방향 전환을 할때 기존에 가고 있던 방향 + 90도 회전이 필요했다는 것이다. 이것은 left, right라는 리스트를 만들어줘서 문제를 해결하였다.

 

from collections import deque

N = int(input())
K = int(input())

apple = []
for i in range(K):
    apple.append(list(map(int, input().split())))

L = int(input())
direction = {}
for i in range(L):
    tmp = list(input().split())
    direction[int(tmp[0])] = tmp[1]

body = deque()  # 뱀의 몸 위치
body.append([1, 1])  # 행, 열
dir_body = [0, 1]  # 처음엔 오른쪽으로 출발
left = [[0, 1], [-1, 0], [0, -1], [1, 0]]
right = [[0, 1], [1, 0], [0, -1], [-1, 0]]
time = 0  # 시간
head = [1, 1]  # 현재 머리 위치


def main():
    global N, K, apple, L, direction, body, dir_body, left, right, time, head

    while True:
        # 방향 전환
        if time in direction:
            if direction[time] == "L":  # 왼쪽으로 90
                idx = left.index(dir_body)
                if len(left) == idx + 1:
                    dir_body = left[0]
                else:
                    dir_body = left[idx + 1]
            elif direction[time] == "D":  # 오른쪽으로 90
                idx = right.index(dir_body)
                if len(right) == idx + 1:
                    dir_body = right[0]
                else:
                    dir_body = right[idx + 1]

        # 머리부터 이동
        head = [head[0] + dir_body[0], head[1] + dir_body[1]]
        # 사과가 있다면 머리 추가하고 꼬리를 빼지 않기 + 사과 제거
        if head in apple:
            time += 1
            body.appendleft(head)
            idx = apple.index(head)
            apple = apple[:idx] + apple[idx + 1:]
        # 사과가 없다면 몸 길이 냅두고 머리 추가하고 꼬리를 빼기
        else:
            time += 1

            # 머리를 추가할건데 그 위치가 벽이거나 자신의 몸이 있는 경우
            if head[0] < 1 or head[0] > N or head[1] < 1 or head[1] > N or (head in body):
                print(time)
                return

            body.appendleft(head)
            body.pop()  # 꼬리 제거

    print(-1)


main()

 

참고