백준 3190 문제 링크

💡 1. 문제 정의

이 문제는 주어진 보드 내에서 적절하게 뱀의 위치를 변경하고 길이를 늘려주는 문제이다.
BFS 알고리즘으로 큐를 활용하여 해결해도 되고, 입력된 보드 자체를 활용하여 구현할 수도 있다.

🤔 2. 해결 방법

입력된 보드 자체를 활용하여 해결$^1$, BFS 알고리즘으로 해결$^2$ 이 2가지 방법으로 문제를 해결해본다.

📑 3. 문제 풀이

3.1 입력된 보드 자체를 활용하여 해결해보기

자료구조 알고리즘에 익숙하지 않아서 처음에는 쌩으로 그냥 구현했다...
이렇게 하다보니 변수들이 너무 많아지고 머리속에서 너무 복잡해지더라ㅜㅜ

n = int(input())
k = int(input())

board = [[0]*n for _ in range(n)] #사과의 위치를 담는다.
board[0][0] = 1 #처음 위치는 무조건 방문처리

for _ in range(k):
    a, b = map(int, input().split())
    board[a-1][b-1] = -1 #사과의 위치에 -1이라는 값을 넣는다.

l = int(input()) #뱀의 방향 변환 횟수
X = []
move = []
for _ in range(l):
    a, b = input().split()
    X.append(int(a)) #x초 후 방향전환
    move.append(b) #'L'은 왼쪽으로 90도 방향전환
                   #'D'는 오른쪽으로 90도 방향전환

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
# 순서대로 오, 위, 왼, 아
direc = 0 #처음 방향은 오른쪽
x, y = 0, 0 #뱀의 머리 좌표
tail = [0, 0] #뱀의 꼬리 위치
time = 1 #게임 시간
flag = False #이중 반복문을 종료할지 판단한다.
m_tail = 1
snake = 1
for n1 in range(n):
    for n2 in range(n):
        if (time-1) in X:
            if move[X.index(time-1)] == 'L':
                # 왼쪽으로 회전
                direc += 1
                if direc > 3:
                    direc = 0
            elif move[X.index(time-1)] == 'D':
                # 오른쪽으로 회전
                direc -= 1
                if direc < 0:
                    direc = 3
        x = x + dx[direc]
        y = y + dy[direc]
        if x >= 0 and x < n and y >= 0 and y < n:
            if board[x][y] != -1 and board[x][y] <= 0:
                # 자기자신의 몸과 부딪히지 않았다면 방문처리한다.
                time += 1

                board[x][y] = snake
                board[tail[0]][tail[1]] = 0
                snake += 1

                for b in range(n):
                    if m_tail in board[b]:
                        t_x = b
                        t_y = board[b].index(m_tail)
                tail = [t_x, t_y]
                m_tail += 1

            elif board[x][y] == -1 and board[x][y] <= 0:
                # 사과가 있고 벽이나 자기자신의 몸과 부딪히지 않았다면 방문처리한다.
                time += 1

                board[x][y] = snake
                snake += 1
            else:
                # 자기자신의 몸과 부딪혔다면 게임을 끝낸다.
                flag = True
                break
        else:
            # 벽에 부딪혔다면 게임을 끝낸다.
            flag = True
            break
    if flag:
        break
print(time)

사과가 있는 위치에는 -1을 넣어주고 뱀의 몸통이 없는 곳에는 전부 0으로 처리해주었다.
뱀이 지나가는 곳이라면 '뱀의 꼬리 -> 뱀의 머리'까지 1씩 숫자를 증가시키며 해당 보드 위치에 넣어주었다.
따라서 뱀이 사과를 먹지 못해 길이가 길어질 수 없는 상황이라면 뱀의 꼬리부분 위치에 있던 숫자를 0으로 바꿔주었다.
뱀의 꼬리부분 숫자는 0과 -1을 제외한 가장 작은 값으로 m_tail 변수를 사용해 보드 내 m_tail이 존재하는 위치를 찾아 꼬리 위치를 찾아냈다.

3.2 BFS 알고리즘으로 해결 해보기

BFS 알고리즘은 지난 포스팅에서 소개한 바 있다. BFS 알고리즘

따라서 큐를 사용해 구현해보았다.
이처럼 자료구조를 활용해 구현해보니 보다 간편하고 알아보기 쉬운 코드로 변경되었다.

from collections import deque

n = int(input())
k = int(input())

board = [[0]*n for _ in range(n)] #사과의 위치를 담는다.
board[0][0] = 1 #처음 위치는 무조건 방문처리

for _ in range(k):
    a, b = map(int, input().split())
    board[a-1][b-1] = 5 #사과의 위치에 5라는 값을 넣는다.

l = int(input()) #뱀의 방향 변환 횟수
X = []
move = []
for _ in range(l):
    a, b = input().split()
    X.append(int(a)) #x초 후 방향전환
    move.append(b) #'L'은 왼쪽으로 90도 방향전환
                   #'D'는 오른쪽으로 90도 방향전환

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
# 순서대로 오, 위, 왼, 아
direc = 0 #처음 방향은 오른쪽
x, y = 0, 0 #뱀의 머리 좌표
q = deque() #뱀의 위치를 담을 큐
q.append((x, y))
time = 1 #게임시간

def turn(d, m):
    if m == 'L':
        d += 1
        if d > 3:
            d = 0
    elif m == 'D':
        d -= 1
        if d < 0:
            d = 3
    return d

while True:
    # 방향 전환 시
    if (time-1) in X:
        direc = turn(direc, move[X.index(time-1)])

    x = x + dx[direc]
    y = y + dy[direc]

    if x < 0 or x >= n or y < 0 or y >= n:
        break
    if board[x][y] != 5 and board[x][y] == 0:
        # 사과가 없고
        # 자기자신의 몸과 부딪히지 않았다면 방문처리한다.
        time += 1

        board[x][y] = 1
        q.append((x, y))
        tx, ty = q.popleft()
        board[tx][ty] = 0

    elif board[x][y] == 5:
        # 사과가 있다면
        time += 1

        q.append((x, y))
    else:
        break

print(time)