[python] 백준 3190번 뱀

백준 3190번 뱀

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

문제

풀이

n = int(input())
k = int(input())
apple = []
for _ in range(k):
    apple.append(list(map(int, input().split())))

map = [[0] * n for _ in range(n)]
for row, col in apple:
    map[row-1][col-1] = 1


# 뱀의 방향 변환 횟수 
l = int(input())

direction = []
time = []
for _ in range(l):
    a,b = input().split()
    time.append(int(a))
    direction.append(b)

row, col = 0, 0
second = 0
snake = [(row, col)]
current_direction = 0  # 0: 동, 1: 남, 2: 서, 3: 북

# 동, 남, 서, 북 이동 방향 설정
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


while True:
    # 다음 위치로 이동
    row += dr[current_direction]
    col += dc[current_direction]
    second += 1

    # 벽에 부딪히거나, 자기 자신의 몸에 부딪히면 게임 종료
    if not (0 <= row < n and 0 <= col < n) or (row, col) in snake:
        break

    # 사과가 있는 경우
    if map[row][col] == 1:
        map[row][col] = 0  # 사과 먹기
    else:
        snake.pop(0)  # 꼬리 이동        
    
    # 뱀의 새로운 머리 추가
    snake.append((row, col))

    # 방향 변환 시간에 도달했을 경우
    if time and second == time[0]:
        if direction[0] == 'L':  # 왼쪽 회전
            current_direction = (current_direction - 1) % 4
        elif direction[0] == 'D':  # 오른쪽 회전
            current_direction = (current_direction + 1) % 4
        time.pop(0)
        direction.pop(0)

print(second)

📌 주의

• 무조건 뱀의 새로운 머리를 추가하고, 사과가 없을 경우 꼬리를 제거한다.
• 이 문제에서 내가 생각하는 핵심은 방향이동이다. # 0: 동, 1: 남, 2: 서, 3: 북 으로 두고,

dr = [0, 1, 0, -1] # 행의 변화
dc = [1, 0, -1, 0] # 열의 변화

동쪽 (current_direction = 0):
dr[0] = 0 (행은 변화하지 않음)
dc[0] = 1 (열이 1 증가, 즉 오른쪽으로 이동)

남쪽 (current_direction = 1):
dr[1] = 1 (행이 1 증가, 즉 아래쪽으로 이동)
dc[1] = 0 (열은 변화하지 않음)

서쪽 (current_direction = 2):
dr[2] = 0 (행은 변화하지 않음)
dc[2] = -1 (열이 1 감소, 즉 왼쪽으로 이동)

북쪽 (current_direction = 3):
dr[3] = -1 (행이 1 감소, 즉 위쪽으로 이동)
dc[3] = 0 (열은 변화하지 않음)

그래서 이동을 계산하면

row += dr[current_direction]
col += dc[current_direction]

방향 전환의 경우

if direction[0] == 'L':  # 왼쪽 회전
    current_direction = (current_direction - 1) % 4
elif direction[0] == 'D':  # 오른쪽 회전
    current_direction = (current_direction + 1) % 4

% 4 연산은 방향 값이 0 미만으로 내려가는 것을 방지한다. 예를 들어 0 (동) 에서 90도 왼쪽 회전을 위해 -1 을 하면 -1 이 되어버린다. 하지만 -1 % 4 를 하면 3으로 (북) 올바른 방향으로 변환된다.