문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
입력
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100)
다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데,
첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다.
사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며.
게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D') 로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
예제 입력 1
6 (N x N, 맵)
3 (사과의 개수)
3 4
2 5
5 3
3 (방향 변환 횟수)
3 D / 오른쪽(C가 'D')
15 L / 왼쪽(C가 'L')
17 D / 오른쪽(C가 '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
n = int(input())
k = int(input())
graph = [[0] * n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(k):
a, b = map(int, input().split())
graph[a - 1][b - 1] = 2
l = int(input())
dirDict = dict()
queue = deque()
queue.append((0, 0))
for i in range(l):
x, c = input().split()
dirDict[int(x)] = c
x, y = 0, 0
graph[x][y] = 1
cnt = 0
direction = 0
def turn(alpha):
global direction
if alpha == 'L':
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
while True:
cnt += 1
x += dx[direction]
y += dy[direction]
if x < 0 or x >= n or y < 0 or y >= n:
break
if graph[x][y] == 2:
graph[x][y] = 1
queue.append((x, y))
if cnt in dirDict:
turn(dirDict[cnt])
elif graph[x][y] == 0:
graph[x][y] = 1
queue.append((x, y))
tx, ty = queue.popleft()
graph[tx][ty] = 0
if cnt in dirDict:
turn(dirDict[cnt])
else:
break
print(cnt)컴파일오류(밑에)
n = int(input())
k = int(input())
data [[0] * (n+1) for _ in range(n + 1)] # 맵 정보
info = [] #방향 회전 정보
# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
a, b = map(int, input().split())
data[a][b] = 1
# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
x, c = input().split()
info.append((int(x), c))
# 처음에는 오른쪽을 보고 있으므로(동, 서, 남, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def turn(direction, c):
if c == "L":
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
return direction
def simulate():
x, y = 1, 1 #뱀의 머리 위치
data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
direction = 0 #처음에는 동쪽을 보고 있음
time = 0
index = 0
q = [(x, y)]
while True:
nx = x + dx[direction]
ny = y + dy[direction]
# 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
# 사과가 없다면 이동 후에 꼬리 제거
if data[nx][ny] == 0:
data[nx][ny] = 2
q.append((nx, ny))
px, py = q.pop(0)
data[nx][ny] = 0
# 사과가 있다면 이동 후에 꼬리 그대로 두기
if data[nx][ny] == 1:
data[nx][ny] = 2
q.append((nx, ny))
# 벽이나 뱀의 몸통과 부딪혔다면
else:
time += 1
break
x, y = nx, ny # 다음 위치로 머리를 이동
time += 1
if index <1 and time == info[index][0]: # 회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
print(simulate())큐를 이용한 구현 문제로 다음과 같이 접근하였다.
① 먼저 그래프(맵)을 모두 0으로 채워준다.
② 사과 위치는 모두 2로 채워준다.
③ 앞으로 뱀이 차지하고 있는 부분은 1로 채워줄 것이다.
④ 뱀이 이동할 때 마다 머리와 꼬리는 한 칸씩 전진한다. (즉, 몸의 길이는 그대로이다.)
⑤ 이동했을 때 사과를 먹으면 머리는 전진하지만 꼬리는 그대로이다. (즉, 몸의 길이가 한 칸 늘어난다.)
⑥ 방향 전환을 해야 하는 타이밍에 맞춰 L이면 왼쪽, D이면 오른쪽으로 방향전환을 한다.
이렇게 무엇을 구현해야 할 지를 정리한 후에 이를 하나씩 차례차례 구현해주면 된다.
①②③ 은 그대로 구현을 하면 되기 때문에 따로 설명은 하지 않고
④의 경우에는 처음 시작 할 때, [0, 0]을 큐에 넣어 몸길이 1 뱀의 초기 위치 상태를 저장하고,
오른쪽으로 한 칸 이동하여 [0, 0]을 큐에서 pop하고
[0, 1]을 큐에 push하여 뱀의 위치 상태를 변경한다.
이런 식으로 뱀을 전진시키면 된다. ( 큐를 뱀의 몸을 나타낸다고 생각하면 된다. )
⑤의 경우는 graph[x][y] = 2일 때 이다. 머리만 전진하면 되므로 큐에서 pop을 하지 않고,
큐에 현재 머리 위치만 push함으로써 뱀의 몸 길이를 늘려준다.
⑥의 경우에는 현재 시간이 방향전환을 해야 하는 시간이면, 입력한 방향에 맞게 전환을 해주면 된다.
(딕셔너리를 이용해 시간을 키값으로, 방향을 밸류값으로 입력받았다.)
from collections import deque
n = int(input())
k = int(input())
graph = [[0] * n for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(k):
a, b = map(int, input().split())
graph[a - 1][b - 1] = 2
l = int(input())
dirDict = dict()
queue = deque()
queue.append((0, 0))
for i in range(l):
x, c = input().split()
dirDict[int(x)] = c
x, y = 0, 0
graph[x][y] = 1
cnt = 0
direction = 0
def turn(alpha):
global direction
if alpha == 'L':
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
while True:
cnt += 1
x += dx[direction]
y += dy[direction]
if x < 0 or x >= n or y < 0 or y >= n:
break
if graph[x][y] == 2:
graph[x][y] = 1
queue.append((x, y))
if cnt in dirDict:
turn(dirDict[cnt])
elif graph[x][y] == 0:
graph[x][y] = 1
queue.append((x, y))
tx, ty = queue.popleft()
graph[tx][ty] = 0
if cnt in dirDict:
turn(dirDict[cnt])
else:
break
print(cnt)deque 사용
from collections import deque
n = int(input())
k = int(input())
array = [[0] * n for _ in range(n)]
apple = 1
for _ in range(k):
a, b = map(int, input().split())
array[a-1][b-1] = apple
L = int(input())
info = []
for _ in range(L):
time, direction = input().split()
info.append((int(time), direction))
# 첫 방향이 동쪽을 바라보고 있다고 주어짐: 동 -> 남 -> 서 -> 북(오른쪽) / 동 -> 북 -> 서 -> 남(왼쪽) => 이를 일직선 상에 세운다고 생각
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def turn_direction(direction, c):
if c == 'L':
direction = (direction - 1) % 4 # 왼쪽 방향으로
else:
direction = (direction + 1) % 4 # 오른쪽 방향으로
return direction
x, y = 0, 0
array[x][y] = 2
direction = 0
info_idx = 0
count = 0
q = deque([(x, y)]) # 뱀 길이 저장할 위치(꼬리 ~ 몸통 ~ 머리)
while True:
nx, ny = x + dx[direction], y + dy[direction]
# 보드 안쪽이거나 뱀 길이 맞닿지 않을 때
if 0 <= nx < n and 0 <= ny < n and array[nx][ny] != 2:
# 다음칸 이동한 곳에 사과가 없을 경우 -> 길이 늘리지 않고 다음칸으로만 이동
if array[nx][ny] == 0:
array[nx][ny] = 2
q.append((nx, ny))
px, py = q.popleft()
array[px][py] = 0
else:
array[nx][ny] = 2
q.append((nx, ny))
else:
count += 1
break
count += 1
x, y = nx, ny
# 시간이 지나가다가 방향 전환 시간 되었을 때
if info_idx < L and count == info[info_idx][0]:
direction = turn_direction(direction, info[info_idx][1])
info_idx += 1
print(count)