[백준] 3190 뱀 (Python/파이썬)

<문제 링크>

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

3190번: 뱀

<풀이 전략>

1. 큐의 선입선출 구조를 활용한 구현 문제이다.
2. 구현해야할 사항들은 간략하게 나눠보면 다음과 같다.
   1. 뱀의 이동
   2. 게임 종료 조건
      • 벽에 부딪혔을 때(= 범위를 벗어났을 때)
      • 뱀의 몸통에 부딪혔을 때
   3. 사과가 있을 때 뱀의 크기를 사과가 있는 영역 한 칸만큼 늘려준다.
   4. 사과가 없을 때 뱀의 크기를 유지한 채 사과가 있는 영역으로 한 칸 이동 시켜준다.(꼬리 -1)
3. 뱀의 몸통은 뱀이 이동하는 경로를 표시해주는 방식으로 구현하고
4. 뱀의 이동은 큐를 이용해서 머리칸을 한 칸씩 큐에 append 해주고, 사과가 없으면 popleft로 꼬리가 있던 영역을 다시 0으로 돌려주는 방식으로 구현했다.
5. 그 외 주의할 사항으로는
   1. 뱀이 이동을 마치고 방향 전환을 한다는 점
   2. 문제에서 인덱스는 1부터 시작한다는 점

<정답 코드>

# 220830 3190 뱀

# 정답코드

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

# N: 배열의 크기, board: 뱀이 이동하는 배열
N = int(input())
board = [[0 for _ in range(N)] for _ in range(N)]

# K: 사과의 개수
# 사과의 위치를 배열에 표시(문제에선 1-index이기 때문에 -1)
K = int(input())
for _ in range(K):
    r, c = map(int, input().split())
    board[r- 1][c- 1] = 2

# L: 방향전환 횟수, turn: 방향전환 정보를 담을 딕셔너리
L = int(input())
turn = dict()
for _ in range(L):
    cnt, direction = input().split()
    turn[int(cnt)] = direction

# 탐색 방향 (처음에 오른쪽을 향하고 있으므로 오른쪽을 바라봤을 때 기준으로 시계방향)
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


# snake: 뱀 이동 함수
def snake(r, c):
    # cnt: 이동 횟수, d: 탐색 방향 조절 변수, snake_q: 뱀의 위치를 나타낼 큐
    cnt = 0
    d = 0
    snake_q = deque()

    # 처음 뱀의 출발점 표시
    board[r][c] = 1
    snake_q.append((r, c))

    while True:

        # 이동 횟수를 세주고 탐색 방향대로 이동
        cnt += 1
        nr = r + dr[d]
        nc = c + dc[d]
        
        # 범위를 벗어나면 게임 종료
        if not 0 <= nr < N or not 0 <= nc < N:
            break
        
        # 이동 위치에 사과가 있을 떄
        if board[nr][nc] == 2:
            # 이동 위치를 표시해주고 뱀의 위치를 큐에 넣어준다.
            board[nr][nc] = 1
            r, c = nr, nc
            snake_q.append((r, c))
        
        # 이동 위치에 사과가 없을 때
        elif board[nr][nc] == 0:
            # 이동 위치를 표시해주고 뱀의 위치를 큐에 넣어준다.
            board[nr][nc] = 1
            r, c = nr, nc
            snake_q.append((r, c))
            # 뱀의 꼬리를 없애준다.
            r_tail, c_tail = snake_q.popleft()
            board[r_tail][c_tail] = 0
        
        # 뱀의 몸통에 부딪혔을 때 게임 종료
        else:
            break
        
        # 이동을 마친 뒤 해당 시행에서 방향 전환을 해야할 때
        if cnt in turn:
            # 좌회전
            if turn[cnt] == 'L':
                d = (d - 1) % 4
            # 우회전
            else:
                d = (d + 1) % 4
    
    # 이동 횟수를 출력하고 함수 종료
    print(cnt)
    return

# 출발점에서부터 뱀 이동
snake(0, 0)