백준 3190 뱀 (골드 4)

백준 3190 뱀 (골드 4)

링크: 3190 시뮬레이션

---

접근 방법

• 그래프 문제로 풀이
• 사과와 빈칸, 뱀칸을 구분해서 처리

---

소스 코드

소스 코드: 시뮬레이션 알고리즘

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
K = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
for k in range(K):
    x, y = map(int, input().split())    
    graph[x-1][y-1] = 2 # 사과는 2

rotate = {}
move = [(0, 1), (-1, 0), (0, -1), (1, 0)]
L = int(input())
for l in range(L):
    tim, rot = input().rstrip().split()
    tim = int(tim)

    if rot == 'L':    
        rotate[tim] = 1
    else: # elif rot == 'D':
        rotate[tim] = -1

direction = 0
time = 1
x = 0; y = 0
queue = deque()
queue.append((0, 0))
while 1:
    new_x = x + move[direction][0]
    new_y = y + move[direction][1]

    if 0 <= new_x < N and 0 <= new_y < N:
        if graph[new_x][new_y] == 2:
            graph[new_x][new_y] = 0
            queue.append((new_x, new_y))
        elif graph[new_x][new_y] == 0 and (new_x, new_y) not in queue:
            queue.popleft()
            queue.append((new_x, new_y))
        else:
            break
    else:
        break

    if time in rotate:
        direction = (direction + rotate[time]) % 4

    time += 1
    x = new_x
    y = new_y

print(time)

---

코드 개선 사항(GPT 4o)

• 없음

결론

• 시뮬레이션에서 뱀의 위치 처리를 어떻게 해야될까 고민했는데, 힌트에서 큐를 사용해서 풀으라해서 유레카! 하고 푼 것 같다.