[Impl] BOJ 3190 뱀

 

🎈 백준 3190 뱀

www.acmicpc.net/problem/3190

3190번: 뱀

 

❗ 문제의 핵심, 풀이 과정

• 사과가 있는 칸과 없는 칸, 그리고 몸이 있는 칸을 구분하여야 한다.

=> 사과가 있는 칸은 1, 사과가 없는 칸은 0, 자신의 몸이 있는 칸은 -1 로 설정한다.

 

• 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

=> 종료 조건:

     - 벽 : nx < 1 or nx > n or ny < 1 or ny > n 

     - 자신의 몸 : graph[nx][ny] == -1

 

• 방향 변환 횟수 (idx)가 남아있고, 방향을 바꿀 때라면 방향 정보를 통해 해당 방향으로 회전한다.

=> 현재 방향 d를 이용해서 조작한다.

 

• 그 외의 차례는 현재 d의 방향으로 다음칸으로 이동하며 종료조건인지 확인한다.

=> 현재 d의 방향으로 다음칸을 가는 함수 go를 설정하여 움직인다.

=> 사과가 없을 경우 꼬리에 위치한 칸을 비워주어야 함으로, 뱀이 이동할 때마다 머리의 위치를 큐에 넣어준다.

 

✅ 전체 코드

import sys
from collections import deque
input = sys.stdin.readline

# 반시계 방향 우, 하, 좌, 상
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# d 방향으로 다음칸
def go():
    global sec, x, y
    nx = x + dx[d]
    ny = y + dy[d]
    # 머리가 벽에 닿았을 때
    if nx < 1 or nx > n or ny < 1 or ny > n:
        print(sec+1)
        exit()
    # 머리가 자신의 몸과 닿았을 때
    if graph[nx][ny] == -1:
        print(sec+1)
        exit()
    q.append((nx, ny))
    # 사과가 있으면 사과 없애고 자신 몸
    if graph[nx][ny] == 1:
        graph[nx][ny] = -1
    # 사과가 없을 때 몸 줄임
    elif graph[nx][ny] == 0:
        graph[nx][ny] = -1
        tx, ty = q.popleft()
        graph[tx][ty] = 0
    x, y = nx, ny
    sec += 1

n = int(input())
k = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
info = []

for _ in range(k):
    a, b = map(int, input().split())
    graph[a][b] = 1

l = int(input())
for _ in range(l):
    a, b = input().split()
    info.append((int(a), b))

q = deque()
x, y = 1, 1
graph[x][y] = -1
q.append((x, y))
sec = 0
d = 0
idx = 0

while True:
    # 방향 변환 횟수가 남아있고, 방향을 바꿀 때라면
    if idx < l and sec == info[idx][0]:
        if info[idx][1] == 'L':
            d = (d+1) % 4
        else:
            d = (d-1) % 4
        idx += 1
    go()