[정글 알고리즘] - [중] - 백준3190 큐 - 뱀 (백준 골드4)

알고리즘 트릭보다 구현 시뮬레이션이 핵심인 문제. 뱀 몸을 리스트(또는 deque)로 관리하고, 매 초마다 이동→충돌→사과→방향 순서를 정확히 따르면 된다. 리스트만으로도 풀 수 있고, 이 글에서는 deque 없이 순수 리스트 버전으로 설명한다.

📋 문제 소개

항목	내용
문제 번호	백준 3190
난이도	골드 4
분류	구현, 시뮬레이션, 큐
핵심 자료구조	리스트(뱀 몸 관리), 딕셔너리(방향 전환 정보)
N 범위	2 ≤ N ≤ 100 (보드 크기)
시간 제한	1초

입력 예시	출력 예시
6 3 3 4 2 5 5 3 3 3 D 15 L 17 D	9

🔄 매 초 시뮬레이션 흐름

이 문제의 전체 구조는 아래 순서를 무한 반복하는 것이다.

순서	동작	코드 역할
①	시간 1 증가	time += 1
②	머리 다음 칸 계산	nx = head_x + dx[dir]
③	벽 / 자기 몸 충돌 검사 → 충돌이면 종료	if 범위 밖 or board==2: break
④	새 머리 위치 추가	snake.append((nx, ny))
⑤	사과 있으면 꼬리 유지 (길이 증가)	if board==1: (꼬리 안 뺌)
⑥	사과 없으면 꼬리 제거 (길이 유지)	else: snake.pop(0), board=0
⑦	해당 시각 방향 전환 명령 있으면 회전	if time in turn: dir 변경

순서 주의: 방향 전환은 항상 이동이 끝난 뒤에 적용된다. "X초가 끝난 뒤" 라는 문제 표현 그대로다.

🗂️ 보드 상태 정의

값	의미	처리
0	빈 칸	이동 가능, 사과 없으므로 꼬리 제거
1	사과	이동 가능, 꼬리 유지 (길이 증가)
2	뱀 몸	충돌 → 게임 종료

보드 1개로 3가지 상태 관리: 보드에 뱀 몸(2)을 표시해두면 if board[nx][ny] == 2 한 줄로 자기 몸 충돌과 벽 충돌을 분리해서 검사할 수 있다.

🧭 방향 시스템 — dx, dy 배열

dir	방향	dx (행 변화)	dy (열 변화)	다음 위치
0	오른쪽 →	0	+1	(x, y+1)
1	아래 ↓	+1	0	(x+1, y)
2	왼쪽 ←	0	-1	(x, y-1)
3	위 ↑	-1	0	(x-1, y)

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

명령	회전 방향	연산	예 (dir=3→위)	결과
D	시계 방향 (오른쪽)	(dir+1)%4	(3+1)%4 = 0	오른쪽 →
L	반시계 방향 (왼쪽)	(dir-1)%4	(3-1)%4 = 2	왼쪽 ←

%4의 의미: 방향 값이 0~3 범위를 벗어나지 않게 하는 순환 처리다. dir=3일 때 D 회전하면 4%4=0으로 돌아오고, dir=0일 때 L 회전하면 (-1)%4=3 (파이썬 음수 나머지는 자동 처리)이 된다.

🐍 뱀 몸 관리 — 리스트로도 된다

뱀 몸은 리스트 하나로 관리한다. 마지막 원소 = 머리, 첫 번째 원소 = 꼬리로 약속한다.

동작	리스트 코드	시간복잡도	설명
머리 추가	snake.append((nx,ny))	O(1)	리스트 뒤에 추가 → 빠름
꼬리 제거	snake.pop(0)	O(N)	앞 원소 제거 시 뒤 전체 이동
현재 머리 조회	snake[-1]	O(1)	마지막 원소 직접 접근

이 문제에서 리스트가 통과되는 이유: N ≤ 100이라 보드가 최대 10,000칸. 뱀 몸 길이도 최대 10,000 이하라 pop(0)의 O(N)이 문제가 되지 않는다.

list (이 문제)	deque (더 빠른 방법)
snake = [(0, 0)] snake.append((nx, ny)) # O(1) snake.pop(0) # O(N) ← 느림 # N≤100이라 통과 가능	from collections import deque snake = deque([(0, 0)]) snake.append((nx, ny)) # O(1) snake.popleft() # O(1) ← 빠름 # 대규모 문제에 적합

🔬 단계별 시뮬레이션 (예제 1 — 4×4 단순 예시)

초기 상태: N=4, 사과 없음, 방향 전환 없음. 뱀 시작 위치 (0,0), 방향: 오른쪽(dir=0)

초기 보드 (S=뱀머리, .=빈칸)

S	.	.	.
.	.	.	.
.	.	.	.
.	.	.	.

time	dir	머리 이동	보드값	꼬리 처리	snake 상태
0	0 (→)	—	—	—	[(0,0)]
1	0 (→)	(0,0)→(0,1)	0 (빈칸)	꼬리(0,0) 제거	[(0,1)]
2	0 (→)	(0,1)→(0,2)	0 (빈칸)	꼬리(0,1) 제거	[(0,2)]
3	0 (→)	(0,2)→(0,3)	0 (빈칸)	꼬리(0,2) 제거	[(0,3)]
4	0 (→)	(0,3)→(0,4)	벽!	—	break → 출력: 4

🍎 사과가 있을 때 — 길이 증가 비교

snake = [(0,0), (0,1)] (꼬리=왼쪽, 머리=오른쪽), 오른쪽으로 이동

🍎 (0,2)에 사과 있을 때	· (0,2)가 빈 칸일 때
머리만 추가, 꼬리 유지 append((0,2)) # 머리 추가 # board[0][2] = 1 → 2 # popleft/pop(0) 없음 결과: [(0,0), (0,1), (0,2)] 꼬리 머리 길이: 3 (증가)	머리 추가 후 꼬리 제거 append((0,2)) # 머리 추가 pop(0) # 꼬리(0,0) 제거 board[0][0] = 0 결과: [(0,1), (0,2)] 꼬리 머리 길이: 2 (유지)

🧩 코드 한 줄씩 이해하기

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

board = [[0]*n for _ in range(n)]    # (1) n×n 보드: 0=빈칸

for _ in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1              # (2) 사과 위치 표시. 입력은 1-based → 0-based 변환

l = int(input())
turn = {}
for _ in range(l):
    x, c = input().split()
    turn[int(x)] = c                 # (3) turn[시각] = 'L' or 'D'

dx = [0, 1, 0, -1]                  # (4) 오른쪽/아래/왼쪽/위
dy = [1, 0, -1, 0]

direction = 0                        # (5) 처음엔 오른쪽(dir=0)
time = 0

snake = [(0, 0)]                     # (6) 뱀 시작 위치 (1행1열 = 인덱스 0,0)
board[0][0] = 2                      # (7) 뱀 초기 위치 표시

while True:
    time += 1

    head_x, head_y = snake[-1]       # (8) 현재 머리 좌표 (마지막 원소)
    nx = head_x + dx[direction]
    ny = head_y + dy[direction]      # (9) 다음 이동 위치 계산

    if nx < 0 or nx >= n or ny < 0 or ny >= n:  # (10) 벽 충돌
        break

    if board[nx][ny] == 2:           # (11) 자기 몸 충돌
        break

    if board[nx][ny] == 1:           # (12) 사과: 머리만 추가, 꼬리 유지
        snake.append((nx, ny))
        board[nx][ny] = 2

    else:                            # (13) 빈 칸: 머리 추가 + 꼬리 제거
        snake.append((nx, ny))
        board[nx][ny] = 2
        tail_x, tail_y = snake.pop(0)
        board[tail_x][tail_y] = 0   # (14) 꼬리 자리를 빈 칸으로

    if time in turn:                 # (15) 이 시각에 방향 전환 명령 있으면
        if turn[time] == 'D':
            direction = (direction + 1) % 4
        else:
            direction = (direction - 1) % 4

print(time)

라인	핵심 포인트
(2)	입력이 1-based이므로 반드시 x-1, y-1로 변환
(8)	snake[-1] = 리스트 마지막 원소 = 머리. O(1) 접근
(14)	꼬리 제거 후 보드도 0으로 초기화해야 충돌 검사가 올바름
(15)	방향 전환은 이동 완료 후 적용. "X초가 끝난 뒤" = 이동 먼저, 회전 나중

⚠️ 흔히 겪는 실수

#	실수	결과	해결
1	입력 좌표를 그대로 사용 (board[x][y])	사과 위치가 한 칸씩 밀림	board[x-1][y-1]로 변환
2	꼬리 제거 후 보드 업데이트 안 함	빈 칸에 뱀(2) 표시 남아 충돌 오판	board[tail_x][tail_y] = 0
3	방향 전환을 이동 전에 적용	잘못된 방향으로 이동	while 루프 끝에서 방향 변경
4	(dir-1)%4 대신 dir-1만 사용	dir=-1이 되어 dx[-1]=dx[3]로 잘못 동작	항상 (dir-1)%4 사용
5	snake[0]을 머리로 착각	머리/꼬리 방향 반대로 처리	snake[-1] = 머리, snake[0] = 꼬리로 약속 고정

📊 예제 1 전체 시뮬레이션 (N=6, 사과 3개)

사과 위치(0-based): (2,3), (1,4), (4,2) | 방향 전환: 3초→D, 15초→L, 17초→D

time	dir	머리 이동	보드값	꼬리 처리	방향 전환	snake 길이
1	→	(0,0)→(0,1)	0	꼬리 제거	—	1
2	→	(0,1)→(0,2)	0	꼬리 제거	—	1
3	→	(0,2)→(0,3)	0	꼬리 제거	D → ↓	1
4	↓	(0,3)→(1,3)	0	꼬리 제거	—	1
5	↓	(1,3)→(2,3)	🍎 사과!	꼬리 유지	—	2 (증가)
6	↓	(2,3)→(3,3)	0	꼬리 제거	—	2
7	↓	(3,3)→(4,3)	0	꼬리 제거	—	2
8	↓	(4,3)→(5,3)	0	꼬리 제거	—	2
9	↓	(5,3)→(6,3)	벽!	—	—	break → 출력: 9

✅ 최종 코드 (deque 없는 순수 리스트 버전)

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

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

for _ in range(k):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1          # 사과: 1-based → 0-based

l = int(input())
turn = {}
for _ in range(l):
    x, c = input().split()
    turn[int(x)] = c              # turn[시각] = 'L' or 'D'

dx = [0, 1, 0, -1]               # 오른쪽, 아래, 왼쪽, 위
dy = [1, 0, -1, 0]

direction = 0                     # 초기 방향: 오른쪽
time = 0

snake = [(0, 0)]                  # 뱀 몸 (마지막=머리, 첫번째=꼬리)
board[0][0] = 2

while True:
    time += 1

    head_x, head_y = snake[-1]
    nx = head_x + dx[direction]
    ny = head_y + dy[direction]

    if nx < 0 or nx >= n or ny < 0 or ny >= n:   # 벽 충돌
        break

    if board[nx][ny] == 2:                          # 자기 몸 충돌
        break

    if board[nx][ny] == 1:                          # 사과: 꼬리 유지
        snake.append((nx, ny))
        board[nx][ny] = 2
    else:                                           # 빈 칸: 꼬리 제거
        snake.append((nx, ny))
        board[nx][ny] = 2
        tail_x, tail_y = snake.pop(0)
        board[tail_x][tail_y] = 0                   # 꼬리 자리 초기화!

    if time in turn:                                # 방향 전환 (이동 후 적용)
        if turn[time] == 'D':
            direction = (direction + 1) % 4
        else:
            direction = (direction - 1) % 4

print(time)

⏱️ 시간 복잡도

동작	복잡도	N=100 기준
뱀 이동 (1회)	O(뱀 길이)	최대 10,000번 pop(0) 내부 이동
전체 시뮬레이션	O(시간 × 뱀 길이)	최대 10,000 × 10,000 = 10⁸ (경계)
실제 통과	통과	N≤100으로 실제 뱀 길이가 작아 문제없음

💬 마무리

이 문제는 알고리즘 트릭 없이 순서 하나만 틀리면 전부 무너지는 순수 구현 문제다. ① 이동 → ② 충돌 → ③ 사과/꼬리 → ④ 방향 전환 순서를 외우고, 꼬리를 뺀 뒤 보드도 0으로 초기화하는 것을 잊지 않으면 된다.

deque가 있으면 더 빠르지만, N≤100인 이 문제에서는 순수 리스트도 충분하다. 자료구조 선택보다 시뮬레이션 순서가 더 중요하다.