https://www.acmicpc.net/problem/3190
‘Dummy’ 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
전형적인 시뮬레이션 문제이다. 맵위에 뱀의 위치와 사과의 위치를 설정하고 매 시간이 지날때마다 어떻게 달라지는지 확인하고 특정 조건에 도달할경우 종료(시간을 반환)한다.
자주나오는 게임캐릭터의 이동이나 지도문제이다.
지도를 만들고 어떻게 움직이는가 구현하는 것이고 해당하는 조건을 충실하게 따르면 해결할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
n = int(input())
k = int(input())
data = [[0]*(n+1) for _ in range(n+1)] #맵 정보 입력
info = [] #방향 회전 정보
#맵 정보(사과는 1 뱀은 2 나머지 0)
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()
data[px][py] = 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 < l and time == info[index][0]: #회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
print(simulate())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
k = int(input())
data = [[0]*(n+1) for _ in range(n+1)] #맵 정보 입력
info = [] #방향 회전 정보
#맵 정보(사과는 1 뱀은 2 나머지 0)
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))
조건에 따라서 지도의 크기와 사과의 개수를 입력받는다. 그리고 지도는 0으로 초기화를 한다.
방향 회전 정보를 담을 info를 준비를 한다.
이제 가장 먼저 사과의 위치를 정한다. for문을 이용해서 사과의 위치를 설정한다.
회전할 방향의 회전 정보를 입력한다. 그리고 몇칸을 가서, 회전을 하는지 info에 입력을 받아준다.
1
2
3
4
5
6
7
8
9
10
#처음에는 오른쪽을 보고 있으므로(동,남,서,북)
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
dx, dy는 동남서북을 따라간다.
1
2
nx = x + dx[direction]
ny = y + dy[direction]
뒤에 이부분이 나오는데 direction에 따라서(0~3) 방향을 결정하게 된다.
일단 turn이 어떻게 작동하는지 보자
현재 방향(direction)과 어느 방향으로 회전할지 결정하는 c가 있다.
1
direction = turn(direction, info[index][1])
회전할 시간이 되면 위와 같이 작동을 해서 방향을 결정한다.
info를 살펴보면 위와 같이 나온다. 몇번째 회전(index)을 통해서 어떻게 회전을 할지 결정한다.
예를 들어서 첫번째 회전할 시간이 되었고 D를 입력 받았다. 현재 오른쪽을 보고 있는 상황이니 (방향 0)
아래를 보고 있는 남쪽으로 방향을 바꿔야할 것이다(방향 1)
다시 함수를 보자
1
2
3
4
5
6
def turn(direction, c):
if c == 'L':
direction = (direction - 1)%4
else:
direction = (direction + 1)%4
return direction
일단 L 왼쪽 이동이 아니라서 else로 빠지게 된다. direction의 결과값은 1을 리턴한다.
다시 정리를 하면 동 - 남 - 서 - 북 즉 시계방향으로 회전할 것인가 반시계방향으로 회전할 것인가 결정하는 문제가 된다. 시계방향으로 회전을 하게된다면 1을 더해주고 반대방향으로 회전을 하면 1을 빼주게 된다.
무슨 말인지 이해를 못했다면 다시 경우의 수를 생각해보자
| 오른쪽 회전 | 왼쪽 회전 | |
|---|---|---|
| 동(0) | D : 남(1) | L : 북(3) |
| 남(1) | D : 서(2) | L : 동(0) |
| 서(2) | D : 북(3) | L : 남(1) |
| 북(3) | D : 동(0) | L : 서(2) |
그래서 위와 같은 함수가 나온다. 상하좌우 아니다. 그자리에서 오른쪽 왼쪽만 결정하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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()
data[px][py] = 0
#사과가 있다면 이동 후에 꼬리 두기
if data[nx][ny] == 1:
data[nx][ny]=2
q.append((nx,ny))
while 무한루프를 돌려서 확인을 해보자
일단 방향에 따라서 뱀의 머리 위치를 이동시킨다.
그리고 해당 nx,ny의 좌표가 맵의 범위 안에 있으며 뱀의 머리와 뱀의 몸통이 부딪치지 않는다면 if문을 수행한다.
이동하고자 하는 지점에 사과가 없다면 머리를 두고 q에다가 (뱀의 위치)에다가 추가를 하고 마지막에 넣어둔 뱀의 위치를 제거한다.
1
q = [(x,y)]
함수 시작하고 초기 셋팅할때 맨처음 뱀의 위치를 넣어두었다.
그리고 사과가 있다면 이동후에 뱀에다가 추가를 하고 제거를 하지 않는다.
1
2
3
4
5
6
7
8
9
10
11
12
#벽이나 뱀의 모통과 부딪혔다면
else:
time += 1
break
x, y = nx, ny #다음 위치로 이동
time += 1
if index < l and time == info[index][0]: #회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
simulate()
만약 위 조건을 만족하지 못했다면 (지도를 벗어나거나 뱀의 몸통에 걸렸다) 시간을 더해주고 빠져나온다.
그게 아니라면 위치를 이동하고 시간을 더하고 회전을 해야하는지 확인을 하는 작업을 반복한다. 즉 break가 나올때까지 time가 얼마인지 계산하게 되는 것이다.
Comments powered by Disqus.