백준 3190번 뱀

문제 설명

이번 문제는 Dummy라는 도스게임을 제작하는 문제입니다. N * N 정사각 보드위에서 뱀이 매 초마다 아래와 같은 규칙으로 움직이고 사과의 위치와 뱀의 이동경로가 주어질 때, 게임이 몇 초에 끝나는지 계산하는 문제입니다.

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

 

문제 풀이

0. 변수

N=int(input()) # 보드의 크기
K=int(input()) # 사과의 개수
apples=[list(map(int,input().split())) for _ in range(K)] # 사과의 좌표
L=int(input()) # 뱀의 방향 전환 횟수
changes=[input().split() for _ in range(L)] # 뱀의 방향 전환 정보

board=[[0 for _ in range(N+2)] for __ in range(N+2)] # 보드판
# 0->빈 칸 1->사과 2->뱀

head,tail=[1,1],[1,1] # 뱀의 머리와 꼬리 좌표
curves=[] # 뱀의 몸통 중 구부러진 구간의 좌표
time=0 현재 시간
c_i=현재까지 방향전환 횟수
direction=1 # 0:위 1:오 2:아 3:왼

1. 머리 이동

뱀이 이동하는 첫 번째 규칙은 우선 몸의 길이를 늘려 머리를 다음칸에 위치시키는 것입니다.

현재 방향에 따라 머리를 이동시켜 줍니다.

if direction==0:
    head[0]-=1
elif direction==1:
    head[1]+=1
elif direction==2:
    head[0]+=1
else:
    head[1]-=1

 

2. 머리가 벽이나 뱀의 몸통에 부딪히는지 확인

이동한 머리의 위치가 벽이거나, 뱀의 몸통일 경우 그만합니다.

if board[head[0]][head[1]]==2:
    break
if not (0<head[0]<=N and 0<head[1]<=N):
    break

 

3. 꼬리 이동

만약 이동한 머리의 위치에 사과가 있을 경우 꼬리는 이동하지 않습니다.

 

만약 이동한 머리의 위치가 빈 칸일 경우,

우선 꼬리의 좌표는 보드칸에 0으로 표시해줍니다.

현재 꼬리의 좌표가 curves의 첫 번째 원소와 같다면(꼬리가 뱀의 구부러진 구간에 도착했다면) curves의 첫 번째 원소를 pop시켜줍니다.

if board[head[0]][head[1]]==0:
    board[tail[0]][tail[1]]=0
    if curves and tail[0]==curves[0][0] and tail[1]==curves[0][1]:
        curves.pop(0)

그 다음, curves에 원소가 있다면, curves의 첫 번째 원소 좌표와 현재 꼬리의 좌표의 행과 열 중 같은 것을 찾습니다. 만약 행이 같다면 꼬리의 열 좌표를 curves의 첫 번째 원소의 열 쪽으로 한 칸 움직이고, 열이 같다면 꼬리의 행 좌표를 curves의 첫 번째 원소의 행 쪽으로 한칸 움직입니다.

if board[head[0]][head[1]]==0:
    ...

    if curves:
        if curves[0][0]==tail[0]:
            tail[1]+= 1 if curves[0][1]>tail[1] else -1
        else:
            tail[0]+= 1 if  curves[0][0]>tail[0] else -1

curves에 원소가 없다면, 현재 뱀의 몸에 구부러진 구간은 없고 일직선인 상태이므로 꼬리 좌표의 행과 열 중 머리 좌표와 다른 것을 머리 좌표쪽으로 이동시켜줍니다.

if board[head[0]][head[1]]==0:
    if curves:
        ...
    else:
        if head[0]==tail[0]:
            tail[1]+= 1 if head[1]>tail[1] else -1
        else:
            tail[0]+= 1 if head[0]>tail[0] else -1

해당 작업까지 끝났다면 뱀의 머리에 대한 좌표값을 board에 2로 표시합니다.

 

4. 방향 전환

그 다음 해당 초가 끝나기 전에 현재 changes[c_i][0]이 time과 같은지 확인합니다.

changes[c_i][0]==time일 경우 changes[c_i][1]에 따라 방향을 바꿔줍니다.

바뀐 방향 정보를 direction에 담아주고, 해당 구부러진 구간의 좌표를 curves에 append해줍니다.

if c_i<L and changes[c_i][0]==str(time):
    if changes[c_i][1]=='L':
        direction= direction-1 if direction>0 else 3
    else:
        direction= (direction+1)%4
    curves.append([head[0],head[1]])
    c_i+=1

 

위의 작업을 뱀의 머리가 벽이나 뱀의 몸통에 닿지 않을 동안 반복해줍니다.

 

 

해결

이번 문제도 구현 문제로 차근히 풀이해야되는 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/3190

3190번: 뱀

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/3190.py