난이도: 2 / 풀이 시간: 40분
link: https://www.acmicpc.net/problem/3190
Dummy'라는 도스 게임이 있습니다. 이 게임에는 뱀이 나와서 기어 다니는데, 사과를 먹으면 뱀 길이가 늘어납니다. 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝납 니다.
게임은 N X N 정사각 보드 위에서 진행되고, 몇몇간에는 사과가 놓여져 있습니다. 보드의 상하좌 우 끝에는 벽이 있습니다. 게임을 시작할 때 뱀은 맨 위 맨 좌측에 위치하고 뱀의 길이는 1입니다.
뱀은 처음에 오른쪽을 향합니다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따릅니다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킵니다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줍니다. 즉. 몸길이는 변하지 않습 니다.
사과의 위치와 뱀의 이동 경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하세요.
입력 조건
출력 조건
입력 예시 1
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D
출력 예시 1
9
입력 예시 2
10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L
출력 예시 2
21
입력 예시 3
10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L
출력 예시 3
13
풀이 특징
from collections import deque
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
n = int(input())
k = int(input())
graph = [[0]*(n+1) for _ in range(n+1)]
# 사과 정보 입력
for _ in range(k):
a, b = map(int, input().split())
graph[a][b] = 1
# 회전 정보 입력
rotations = []
l = int(input())
for _ in range(l):
x, c = input().split()
rotations.append((int(x), c))
# 시뮬레이션 설정
headX, headY = 1, 1
graph[headX][headY] = 2
direction = 0
time = 0
index = 0 # rotation 인텍스
q = deque()
q.append((headX, headY)) # 뱀이 차지하고 있는 위치 정보
while True:
nextX = headX + move[direction][0]
nextY = headY + move[direction][1]
time += 1
# 이동불가 or 몸통과 만난 경우 종료
if nextX < 1 or nextX > n:
break
if nextY < 1 or nextY > n:
break
if graph[nextX][nextY] == 2:
break
# 사과가 위치한 경우 머리이동
if graph[nextX][nextY] == 1:
headX, headY = nextX, nextY
graph[headX][headY] = 2
q.append((headX, headY))
# 사과가 위치하지 않은 경우 머리이동 후 꼬리위치 제거
if graph[nextX][nextY] == 0:
headX, headY = nextX, nextY
graph[headX][headY] = 2
q.append((headX, headY))
tailX, tailY = q.popleft()
graph[tailX][tailY] = 0
# 회전시간인지 여부 확인
if index < l and rotations[index][0] == time:
if rotations[index][1] == 'L':
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
index += 1
print(time)