백준 3190번 - 뱀

뱀 문제 바로 가기

풀이 날짜: 2026-01-20

baekjoon 알고리즘 문제 풀이

풀이 코드


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

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

board = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(k):
    a,b = map(int, input().split())
    board[a][b] = 1

l = int(input())
turns = {}
for _ in range(l):
    x,c = input().split()
    turns[int(x)] = c

dx = [0,1,0,-1]
dy = [1,0,-1,0]

snake = deque([(1,1)])
board[1][1] = 2

time = 0
dir = 0 #처음엔 오른쪽
x,y = 1,1

while True:
    time+=1
    nx = dx[dir] + x
    ny = dy[dir] + y

    if not (1<=nx<=n and 1<=ny<=n):
        break
    if board[nx][ny] == 2:
        break
    if board[nx][ny] == 1:
        board[nx][ny] = 2
        snake.append((nx,ny))
    else:
        board[nx][ny] = 2
        snake.append((nx,ny))
        tx,ty = snake.popleft()
        board[tx][ty] = 0

    x,y = nx,ny

    if time in turns:
        if turns[time] == 'L':
            dir = (dir + 3)%4
        else:
            dir = (dir + 1)%4
print(time)

print(count)

문제 핵심 요약:

3190번 뱀 문제의 본질은 알고리즘 설계가 아니라 시뮬레이션이다. 매 초마다 “이동 → 충돌 검사 → 상태 갱신 → 방향 전환”이라는 규칙을 그대로 코드로 옮기는 것이 핵심이었다. BFS나 DFS처럼 모든 방향을 탐색하는 문제가 아니라, 현재 상태를 유지하면서 시간에 따라 한 방향으로만 진행하는 문제라는 점을 기억하자.

방향은 ‘탐색 대상’이 아니라 ‘상태 값’이다

이 문제에서 방향은 상하좌우를 전부 시도해 보는 대상이 아니다. 방향은 하나의 변수 (dir)로 설정했고, 특정 시간에만 변경되어야 한다. 따라서 for _ in range(4)와 같은 방식은 문제에 적합하지 않고, 방향은 반복이 아니라 상태로 관리해야 한다는 것이 중요했다.

뱀의 몸 관리는 deque가 핵심이다.

뱀의 길이는 사과를 먹을 때는 늘어나고, 그렇지 않을 때는 유지된다. 이를 구현하기 위해서는 머리는 추가하고 꼬리는 제거하는 구조가 필요했다. 따라서 deque를 사용해 append와 popleft를 통해 머리와 꼬리를 조절했다. 리스트로 구현하면 복잡해지지만, deque를 사용해 실제 뱀의 움직임을 그대로 표현할 수 있다.

“머리 추가 + 꼬리 제거” 규칙을 반드시 분리해서 생각해야 한다

사과가 없을 때는 뱀의 길이가 늘어나지 않는다. 하지만 구현에서는 항상 머리를 먼저 추가했고, 사과가 없는 경우에만 꼬리를 제거하는 방식으로 처리했다.

충돌 검사는 “이동하기 전”에 해야 한다.

다음 칸으로 이동했을 때 벽이나 자기 몸과 충돌하는지를 반드시 이동 처리 전에 검사해야 한다. 이동 후에 검사하면 이미 보드를 갱신한 상태가 되어 논리가 꼬일 수 있다. 시뮬레이션 문제에서는 “다음 상태를 계산 → 유효성 검사 → 실제 반영”의 순서를 지키는 것이 매우 중요하다는 점을 다시 한 번 느꼈다.

방향 전환 정보는 딕셔너리

방향 전환은 특정 시간에만 발생하므로, 이를 리스트로 관리해 매번 순회하기보단 딕셔너리로 time -> 방향 형태로 저장했다. 이렇게 하면 매 초마다 if time in turns로 O(1)에 방향 전환 여부를 확인할 수 있다.

Vienna sausage