[WEEK02/DAY06] 백준 문제 : 뱀

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

3190번: 뱀

 

문제를 푸는 내내 이 노래가 머릿속에 맴돌았다. 나만 당할 순 없지.

 

 

문제 해석 :

N*N 크기의 정사각형 행렬에서 '뱀 게임'을 구현하는 문제이다. 규칙은 다음과 같다.

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

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

보드의 크기는 2 ≤ N ≤ 100 이다. (2차원 행렬로 구현하기에 문제 없는 크기)

사과의 개수는 0 ≤ K ≤ 100 이다.

뱀은 입력받은 시간에 맞춰 방향을 변환하는데, 'D'면 오른쪽, 'L'이면 왼쪽으로 꺾어서 간다.

 

위 조건들을 모두 고려하여 프로그램을 짜서, 게임이 몇 초에 끝나는지를 출력하면 된다.

 

그리고 문제의 조건에 시작시간이 나와있지 않아서 좀 모호한데,

뱀이 초기값인 [0, 0] 에 위치했을 때를 0초로 놓으면 된다.

한 칸 움직이면 그 때 1초로 카운트하면 된다.

그리고 끝나는 기준을 만족했을 때 (예를 들면 뱀의 머리가 벽 위에 박혀있게 될 때)의 시간을 최종적으로 출력해주면 된다.

 

 

접근 :

기본적으로 구현을 어떻게 할지만 생각해내면 그리 어렵지는 않다.

 

• 게임이 진행될 보드 : 2차원 리스트
• 뱀의 이동 구현 : 큐
• 뱀의 방향전환 : 방향전환 정보는 큐에 저장, 방향값 전환은 dict의 key, value값 이용

구체적인 구현은 코드와 함께 알아보자.

 

 

구현 :

일단 N*N의 2차원 리스트를 만들고, 0으로 채워줬다.

그리고 사과가 있는 곳에는 1을 넣어줬다.

 

뱀의 머리가 사과가 있는 곳에 가게 되면 1을 0으로 바꿔주고(사과를 먹고) 꼬리를 가만히 두면 된다.

 

우선 몸이 늘어나서 다음칸에 위치하고, 사과가 없으면 꼬리가 줄어드는 것이기 때문에

사과를 먹으면 몸 길이가 늘어나는 효과가 나는 것이다.

 

나는 뱀을 bam이라는 변수에 큐 구조로 선언했다.

그리고 초기값 [0, 0]을 넣어줬다.

from collections import deque # 를 해서 내장 모듈을 이용했다.

bam = deque()
bam.append([0,0])

 

먼저 뱀이 어느 방향으로 갈지 방향을 정해줘야 한다.

나는 move라는 변수에 방향값을 저장했다.

그리고 turn_D와 turn_L 변수에 key와 value 형태로 꺾었을 때의 방향값을 넣어줬다.

turn_D = {(1,0):(0,-1), (0,1):(1,0), (-1,0):(0,1), (0,-1):(-1,0)}
turn_L = {(1,0):(0,1), (0,1):(-1,0), (-1,0):(0,-1), (0,-1):(1,0)}



# time값에 따른 이동 방향 변경
try:
    if int(turn_info[0][0]) == time:
        if turn_info[0][1] == 'D':
            move = turn_D[move]
        else:
            move = turn_L[move]
        turn_info.popleft()
except: pass

# turn_info라는 큐에 방향 전환할 time값과 'D' or 'L' 값을 저장해 두었다.
# 적용할때마다 하나씩 popleft 하게 되고, 만약 남아있는 값이 없어서 에러가 나게 되면 pass 해준다.

 

그리고 몸 길이를 늘려 다음 칸에 위치시키는 것은, bam에 다음 칸의 값을 삽입하는 것으로 구현했다.

move = (0,1)
# row 좌표는 두고, col 좌표가 1 증가함.
# 오른쪽으로 1 이동하는 것과 같음.

# 몸길이를 늘려 머리를 다음칸에 위치시킨다
# 직전 칸 (bam의 마지막 인덱스) 값에 move 값을 더해줬다.
bam.append([bam[-1][0]+move[0], bam[-1][1]+move[1]])

# 만약 뱀이 -1 인덱스로 움직이면 왼쪽이나 윗쪽 벽에 부딪힌 것이므로 게임을 종료한다.
if bam[-1][0] < 0 or bam[-1][1] < 0:
    return time

 

그리고 이동한 칸에 몸이 있으면 자기 몸에 부딪힌 것이므로, 역시 게임 종료 조건이 된다.

일단 머리를 temp 변수에 빼놓고, 그 값이 자기 몸 안에 있는지를 확인해주었다.

# 이동한 칸에 내 몸이 있나?
temp = bam.pop()
if temp in bam:
    return time
bam.append(temp)

 

그리고 이동한 칸에 사과가 있는지를 확인해 주어야 한다.

이때 index out of range가 발생한다면 뱀이 오른쪽이나 아랫쪽 벽에 부딪힌 것이므로 게임을 종료해준다.

# 이동한 칸에 사과가 있나?
try:
    if arr[bam[-1][0]][bam[-1][1]] == 1:
        arr[bam[-1][0]][bam[-1][1]] = 0
    else:
        bam.popleft()

except: return time

그리고 time을 1 늘려주며 마무리한다.

 

 

 

전체 코드를 보면 이해가 잘 될 것이다. 아마도...

import sys
from collections import deque

def baaam() -> int:
    n = int(input())
    k = int(input())
    arr = [[0]*n for _ in range(n)]

    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        arr[x-1][y-1] = 1
    
    l = int(input())
    turn_info = deque()
    for _ in range(l):
        turn_info.append(sys.stdin.readline().split())

    bam = deque()
    bam.append([0,0])
    move = (0,1)
    time = 0
    turn_D = {(1,0):(0,-1), (0,1):(1,0), (-1,0):(0,1), (0,-1):(-1,0)}
    turn_L = {(1,0):(0,1), (0,1):(-1,0), (-1,0):(0,-1), (0,-1):(1,0)}

    while True:
        # time값에 따른 이동 방향 변경
        try:
            if int(turn_info[0][0]) == time:
                if turn_info[0][1] == 'D':
                    move = turn_D[move]
                else:
                    move = turn_L[move]
                turn_info.popleft()
        except: pass
        
        # 몸길이를 늘려 머리를 다음칸에 위치시킨다
        bam.append([bam[-1][0]+move[0], bam[-1][1]+move[1]])
        if bam[-1][0] < 0 or bam[-1][1] < 0:
            return time

        # 이동한 칸에 내 몸이 있나?
        temp = bam.pop()
        if temp in bam:
            return time
        bam.append(temp)

        # 이동한 칸에 사과가 있나?
        try:
            if arr[bam[-1][0]][bam[-1][1]] == 1:
                arr[bam[-1][0]][bam[-1][1]] = 0
            else:
                bam.popleft()

        except: return time

        time += 1
        


if __name__=='__main__':
    print(baaam()+1)

 

 

그리고 다음 코드를 넣어주면 마치 GUI 같은 CLI 뱀 게임을 즐길 수 있다.

from time import sleep
import copy, os

# 위의 모듈을 추가로 import 해주세요
# 아래 코드는 while문의 맨 끝에 삽입하면 됩니다.


# GUI 뱀 게임

print_arr = copy.deepcopy(arr)
for body in bam:
    print_arr[body[0]][body[1]] = '^'
for i in range(len(print_arr)):
    print(*print_arr[i])
print(f'\ntime : {time}\n')
sleep(1)

# 운영체제에 맞게 주석을 풀어서 쓰세요
# os.system('cls') # windows 운영체제용
# os.system('clear') # linux, mac 운영체제용

디버깅할때 뱀이 어디로 움직이는지가 직관적으로 안 보이는게 화가 나서 짰다.

실제로 꽤 도움이 됐다.