[python] 백준 3190 - 뱀

출처 : 백준, https://www.acmicpc.net/problem/3190

 

 

 

먼저, 생각해야 할 부분

 

1. 계속 움직이는 뱀이 차지하는 좌표들을 어떻게 관리하면 좋을까?

     

     뱀이 자기자신에게 부딪혀도 게임 오버이기 때문에 지속적으로 뱀의 좌표를 관리해주어야한다.

     뱀이 한 번 움직일 때마다 뱀이 차지하는 좌표들을 조회해야했기 때문에 빠르게 조회할 수 있는 자료형이 필요했고,

     처음에는 좌표들을 set에 넣어서 관리하려고 했다.

 

     이를 통해 새 좌표를 넣어주고, 꼬리를 제거하면서 필요 시 간편하게 조회할 수 있을 것이라 생각했다.

     그러나 set은 성분의 순서를 보장하지 않기 때문에 뱀의 꼬리가 어디인지 알아낼 수 없었다.

     이를 해결하기 위해 dictionary 자료형을 사용하도록 변경했다.

      (Python 3.6 이상 버전부터 dict의 순서 보장)

---

 

풀이

 

def findTail(snake): #Python 3.5이하 버전
    return sorted(list(snake.items()), key=lambda x: x[1])[0][0]

def solution(n, k, apple_list, rotation_list):
    # n x n의 판 위에서 뱀은 (0, 0)에서 오른쪽을 향해 시작
    # 보드의 상하좌우 끝에 벽이 존재 -> 보드 밖에 벽이 존재
    # 매 1초마다 뱀은 향하는 방향으로 몸을 늘림
        # 몸을 늘린 방향에 사과가 있으면 꼬리 유지
        # 몸을 늘린 방향에 사과가 없다면 몸을 당김
    # x초가 끝난 뒤에 왼쪽 L또는 오른쪽 D 방향으로 90도 회전
    # 자기 몸에 닿거나 벽에 닿으면 게임 오버

    LEFT = 'L'
    RIGHT = 'D'

    direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 오 하 좌 상 -> 시계 방향
    # D라면 idx + 1
    # L이라면 idx - 1

    dir_idx = 0
    head = (0, 0)
    snake = dict([[ head , 0 ]])

    time = 0

    while True:
        # 1초 시작
        time += 1

        # 머리를 뻗음
        cr, cc = head
        nr = cr + direction[dir_idx][0]
        nc = cc + direction[dir_idx][1]

        # 벽에 부딪히거나 머리가 몸체와 부딫혔을 때 return time
        if not 0 <= nr < n or not 0 <= nc < n or (nr, nc) in snake:
            return time

        snake[(nr, nc)] = time

        #사과가 있다면 사과 제거
        if (nr, nc) in apple_list:
            apple_list.remove((nr, nc))
        else: # 사과가 없다면 snake에서 꼬리 위치 제거
            tail = list(snake.keys())[0]
            snake.pop(tail)

        head = (nr, nc)

        # x초가 끝나면 따라 방향 전환
        if time in rotation_list:
            if rotation_list[time] == LEFT:
                dir_idx = dir_idx - 1 if dir_idx - 1 >= 0 else 3
            else:  # RIGHT
                dir_idx = dir_idx + 1 if dir_idx + 1 < 4 else 0

    return 0

n = int(input())
k = int(input())

apple_list = set([tuple(map(lambda x : int(x) - 1, input().split())) for _ in range(k)])

r = int(input())
rotation_list = dict()

for _ in range(r) :
    x, c = input().split()
    rotation_list[int(x)] = c

print(solution(n, k, apple_list, rotation_list))

 

---

알게 된 점

 

Python의 dictionary에 key로 tuple이 사용 가능한가?

 

사용 가능하다.

 

dictionary에서 key로 제거하기

del dict[key]
dict.pop(key)

 

Dictionary의 순서

dictionary는 python 3.6 이상 버전부터 성분의 순서를 보장한다.

 

 

고찰

 

행과 열

 

사과의 행과 열이 당연히 0, 0부터 시작할 것이라는 생각을 했다. 이 때문에 오래 걸렸다.

문제를 읽을 때, 행과 열이 input으로 주어지면 0부터 시작하는지 1부터 시작하는지 체크하자.

 

문제를 잘 읽자

 

x초가 시작할 때, 회전한다고 생각하고 있었다가 끝난 이후에 방향을 회전하는 것이라는 것을 뒤늦게 알았다.

문제를 꼼꼼히 읽은 후 정리하자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들