🥇[백준] 3190 뱀 (골드4) / 구현, 큐, 이왜틀 극복

문제요약

나의 코드 및 설명 01 - 질문게시판에 있는 반례 다 통과하는데 틀렸습니다 받음 >> 뱀의 꼬리를 제거할 때 잘못함

• 전체 그리드 : board[][]
• 뱀이 있는 좌표 값 : 2
• 사과가 놓인 좌표 값 : 1
• 아무것도 없는 좌표 값 : 0 으로 정의하고 문제를 풀었다.
• 매 초마다 뱀의 움직임을 업데이트하는 move() 함수를 작성하고, 메인 함수 부분의 while문에서 호출하여 뱀이 더 이상 움직일 수 없을 때까지 이동을 반복할 수 있도록 코드를 작성하였다.
• 예제 입력과 질문게시판 반례를 모두 통과하였지만 계속 틀렸다는 판정을 받았다.
• 알고보니, 뱀이 방문할 다음 좌표에 아무것도 없는 경우, 다음 좌표를 2로 업데이트하고, 뱀의 꼬리 부분은 0으로 바꿔주어야 하는데 이 부분이 잘못되었다. 처음엔 뱀의 꼬리 부분의 상하좌우 네 방향을 살펴보고, 단순하게 좌표 값 2인 좌표가 새로운 뱀의 꼬리 좌표가 된다고 생각했는데 여러 번 고민해보니 네 방향 중 2인 좌표는 여러 개일 수 있었다. (뱀이 똬리를 틀고 있는 모양과 같이)

def move(): #뱀의 머리 시작 좌표, 꼬리 좌표
    global d, sx,sy,ex,ey
    nx = sx + dx[d]
    ny = sy + dy[d]
    if nx<0 or nx>=n or ny<0 or ny>=n:
        return False
    else:
        if board[ny][nx] == 2:
            return False #false면 종료
        elif board[ny][nx] == 1: #사과가 있다면
            board[ny][nx] = 2
            sx,sy = nx,ny
            return True
        elif board[ny][nx] == 0:
            board[ny][nx] = 2
            board[ey][ex] = 0
            sx,sy = nx,ny

            ##-------뱀의 꼬리를 찾아서 제거하는 부분이 잘못됨--------# 
            for i in range(4):
                next_ex = ex + dx[i]
                next_ey = ey + dy[i]
                if 0<=next_ex<n and 0<=next_ey<n:
                    if board[next_ey][next_ex] == 2:
                        ex,ey = next_ex,next_ey  
                        break
            ##----------------------------------------------#
            return True


n = int(input())

#뱀은 (0,0), 뱀의 길이 1
#뱀은 처음에 오른쪽

#이동한 칸에 사과 o >> 사과 없어지고 꼬리 그대로
#         사과 x >> 꼬리 비운다
board = [[0 for _ in range(n)] for _ in range(n)]
board[0][0] = 2

k = int(input())
apple = []
for _ in range(k):
    y, x = map(int, input().split())
    board[y-1][x-1] = 1

l = int(input())

d = 0
direction = []
for _ in range(l):
    x, c = input().split()
    direction.append((int(x),c))

dx = [1,0,-1,0] #동 남 서 북
dy = [0,1,0,-1]



sx,sy = 0,0
ex,ey = 0,0
time = 0
turn_t = 0
turn_d = ""
if direction:   
    t_list = direction.pop(0)
    turn_t = t_list[0]
    turn_d = t_list[1]

while True:
    time += 1
    if move() == False:
        break
    if time == turn_t:
        if turn_d == "L":
            d = (d-1)%4
            if direction:
                t_list = direction.pop(0)
                turn_t = t_list[0]
                turn_d = t_list[1]
        else:
            d = (d+1)%4
            if direction:
                t_list = direction.pop(0)
                turn_t = t_list[0]
                turn_d = t_list[1]
    print()
    print("time:",time)
    for i in range(n):
        print(" ".join(map(str, board[i])))

print(time)

나의 코드 및 설명 02 - 큐를 이용하여 문제 해결

• 큐에 뱀의 머리 좌표와 꼬리 좌표를 저장한다.
• while문을 통해 반복할 때 마다 머리 좌표(sx,sy)와 꼬리 좌표(ex,ey) 가 갱신된다.

from collections import deque


n = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
board[0][0] = 2 #최초 뱀의 위치


k = int(input())
for _ in range(k):
    y, x = map(int,input().split())
    board[y-1][x-1] = 1 #사과가 놓인 좌표 체크

l = int(input())
direction = {}
for _ in range(l):
    x, c = input().split() #x초 후에 c로 방향 전환
    direction[int(x)] = c #딕셔너리에 방향 변환 정보 저장

dx = [1,0,-1,0] #동 남 서 북
dy = [0,1,0,-1]

d = 0
sx,sy,ex,ey = 0,0,0,0
snake = deque() #머리 좌표와 꼬리 좌표를 저장할 큐 
snake.append((sx,sy)) # snake = [[꼬리x,꼬리y], [머리x,머리y]]

time = 0
# print()
# for i in range(n):
#     print(" ".join(map(str, board[i])))
while True:
    time += 1
    temp = list(snake) #큐를 리스트로 변환 후
    sx,sy = temp[-1][0], temp[-1][1] #마지막 인덱스 값 : 머리 좌표 
    ex,ey = temp[0][0], temp[0][1] #처음 인덱스 값 : 꼬리 좌표
    
    nx = sx + dx[d]
    ny = sy + dy[d]
    if 0<=nx<n and 0<=ny<n: #다음 좌표가 범위 안에 있을 때
        if board[ny][nx] == 2: #다음 좌표가 몸체이면, 그만이동
            break

        elif board[ny][nx] == 0: #다음 좌표가 사과가 없는 곳이라면
            board[ny][nx] = 2 #일단 머리를 늘린다.
            snake.append((nx,ny)) #새로운 머리 좌표 추가
            board[ey][ex] = 0 #기존의 꼬리 좌표는 비워준다.
            snake.popleft() #꼬리 좌표가 비워졌으니 popleft()로 처음 인덱스 값을 꺼낸다.

        elif board[ny][nx] == 1: #다음 좌표가 사과가 있는 곳이라면
            snake.append((nx,ny)) #머리를 늘린다.
            board[ny][nx] = 2
    else:
        break
    # print(snake)

    if time in direction:
        if direction[time] == "D":
            d = (d+1)%4
        elif direction[time] == "L":
            d = (d-1)%4
    # print()
    # print("time:",time)
    # for i in range(n):
    #     print(" ".join(map(str, board[i])))

print(time)

피드백

2시간 30분정도 헤맸다. 초기에 문제 풀 때는 1시간정도 걸렸었는데, 왜 틀린지 몰라서 많이 헤맸다. 시간 경과에 따른 전체 그리드를 출력하면서 문제를 이해했는데, 이 과정에서 디버깅에 흥미를 느낄 수 있었고, 큐를 이용해 문제를 풀 수 있다는 깨달음도 얻었다.

이번 문제를 통해 행과 열(입력 부분)을 정확히 파악해야겠다고 느꼈다. 풀 때는 한편으로는 답답했지만 정말 재밌게 풀었던 문제이다.