[#3190] 뱀

RookieAND·2022년 12월 8일

구현 그래프 백준 코테

BaekJoon

목록 보기

40/42

❓ Question

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

📖 Before Start

그래프 탐색 으로 지문의 요구사항을 그대로 구현하는 문제였다.

이번 문제는 그래프 탐색 알고리즘을 통해 게임을 구현하는 문제였다.
흔히들 빡구현이라고 많이 부르는 문제였는데, 생각보다 재미있게 풀었다.

✒️ Design Algorithm

뱀의 머리가 벽이나 자신의 몸에 닿는지 를 계속해서 체크해보자.

가로 N 칸, 세로 N 칸의 이차원 배열 내에서 뱀 게임이 진행된다.
뱀의 시작 좌표는 (0, 0) 이며, 처음에는 우측 (동쪽) 을 바라본다고 한다.

이후 사과가 놓인 좌표가 K 개 만큼 주어지는데, 뱀이 이를 먹을 경우 몸이 늘어난다.
즉, 뱀의 머리가 사과가 놓인 좌표에 도달할 경우 몸이 1칸 늘어난다는 의미였다.
따라서 현재 뱀의 몸이 놓인 좌표를 하나의 list 에 보관하여 체크하고자 했다.

이후 방향 변환에 대한 정보가 L 개 만큼 주어지는데, 시계 혹은 반시계 방향이다.
따라서 동남서북 방향에 대한 2차원 벡터가 담긴 값을 하나의 list 에 담아둔 후,
회전 방향에 따라 뱀이 바라보는 위치를 수정하여 적용시키면 될 거라고 생각했다.

💻 Making Own Code

✅ Correct Code

import sys

read = sys.stdin.readline
N, K = int(read()), int(read())
# 좌표의 값은 1부터 시작이기 때문에 이를 맞춰주기 위해서 0부터 시작하도록 1을 감산.
apples = [tuple(map(lambda x: int(x) - 1, read().split())) for _ in range(K)]

L = int(read())
controls = []
for _ in range(L):
    time, dir = read().split()
    controls.append((int(time), -1 if dir == "L" else 1))

# 순서대로 동, 남, 서, 북 방향에 대한 2차원 벡터 (y, x) => (시계 방향 : + 1, 반시계 방향 : - 1)
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
dir_kr = ['동', '남', '서', '북']
snack_body = [(0, 0)]

head_loc = [(0, 0)]
current_time = 0
look_direction = 0 # 오른쪽, 즉 동쪽을 바라보며 시작.
while head_loc:
    current_time += 1
    # 바라보는 방향에 대한 y, x 변화 값을 가져와 더해줌.
    ny, nx = head_loc.pop()
    look_y, look_x = direction[look_direction]
    my, mx = ny + look_y, nx + look_x

    # 가는 길에 사과가 있다면, 해당 좌표까지 몸을 늘인 것.
    if (my, mx) in apples:
        apples.remove((my, mx))
        snack_body.append((my, mx))
        head_loc.append((my, mx))
    # 가는 길에 사과는 없지만, 벽과 몸에 부딪히지 않은 경우 꼬리를 줄인다.
    elif 0 <= my < N and 0 <= mx < N and (my, mx) not in snack_body:
        snack_body.append((my, mx))
        del snack_body[0]
        head_loc.append((my, mx))
    # 그 외의 경우 게임을 종료 시킨다.
    else:
        break

    # 이동을 진행한 후후에, 뱀이 바보는 방향을 변경해야 하는지 체크.
    # 또한 입력 받은 명령을 모두 수행하였는지도 체크해야 함.
    if controls:
        oper_time, oper_dir = controls[0]
        if current_time == oper_time:
            look_direction = (look_direction + oper_dir) % 4
            del controls[0]

print(current_time)