[BFS] 전투 로봇 - 삼성전자
전투 로봇을 BFS를 반복해서 푼 기록입니다. 한 칸씩이 아니라 층 단위로 큐를 비우는 이유와 같은 거리의 몬스터 중 하나를 고르는 자리를 정리합니다.
문제
n x n 격자판에 m개의 몬스터와 하나의 전투로봇이 주어집니다. 한 칸에는 몬스터가 최대 하나만 존재할 수 있습니다.
전투로봇과 몬스터 모두 자연수인 레벨을 가지고 있습니다. 초기의 전투로봇의 레벨은 2이고, 전투로봇은 1초에 상하좌우로 인접한 한 칸씩 이동합니다.
전투로봇은 자신의 레벨보다 큰 몬스터가 있는 칸은 지나칠 수 없고, 나머지 칸은 모두 지날 수 있습니다. 전투로봇은 자신의 레벨보다 낮은 몬스터만 없앨 수 있습니다. 즉 레벨이 같은 몬스터는 없애지는 못하지만, 해당 칸을 지나칠 수는 있습니다.
전투로봇이 어디로 이동할지 정하는 규칙은 다음과 같습니다.
- 없앨 수 있는 몬스터가 있다면 해당 몬스터를 없애러 갑니다.
- 없앨 수 있는 몬스터가 하나 이상이라면, 거리가 가장 가까운 몬스터를 없애러 갑니다.
- 거리는 해당 칸으로 이동할 때 지나야하는 칸의 개수의 최솟값을 뜻합니다.
- 가장 가까운 거리의 없앨 수 있는 몬스터가 하나 이상이라면 가장 위에 존재하는 몬스터를, 가장 위에 존재하는 몬스터가 여럿이라면 가장 왼쪽에 존재하는 몬스터부터 없앱니다.
- 없앨 수 있는 몬스터가 없다면 일을 끝냅니다.
전투로봇이 한 칸 이동하는데에는 1초가 걸리고, 몬스터를 없애는 시간은 없다고 가정합니다. 즉 전투로봇이 목표하는 몬스터가 있는 칸에 도달하면 바로 몬스터가 없어집니다. 몬스터를 없애면 해당 칸은 빈칸이 됩니다.
전투 로봇은 본인의 레벨과 같은 수의 몬스터를 없앨 때마다 레벨이 상승합니다. 예를 들어 레벨이 3인 전투 로봇은 3개의 몬스터를 없애면 레벨이 상승합니다.
다음과 같이 전투 로봇과 몬스터가 있다면 다음과 같이 진행됩니다.
전투로봇이 일을 종료하기까지 총 17초가 걸립니다.
공간에 있는 몬스터와 전투로봇의 정보가 주어질 때, 전투 로봇이 일을 끝내기 전까지 걸린 시간을 출력하세요.
입력
첫 번째 줄에 격자판의 크기를 의미하는 정수 n이 주어집니다.
두 번째 줄부터 (n+1)번째 줄까지 공간에 대한 정보가 공백을 사이에 두고 주어집니다. 0은 빈 곳을 의미하며, 1부터 6까지는 몬스터가 존재하며, 적힌 수는 해당 몬스터의 레벨을 의미합니다. 9는 전투로봇을 의미합니다. 이외의 입력은 주어지지 않습니다.
전투로봇은 무조건 한 곳에 위치한다고 가정해도 좋습니다.
제한 조건
- 2 ≤ n ≤ 20
출력
전투로봇이 일을 끝내기 전까지 걸린 시간을 출력하세요.
입력 예제
예제 1
1
2
3
4
5
6
5
0 0 0 0 0
2 0 0 4 0
0 0 9 0 0
0 0 0 0 0
1 0 0 4 1
1
17
예제 2
1
2
3
4
3
0 1 1
4 4 4
0 9 0
1
0
제한
- Time Limit: 1000 ms
- Memory Limit: 80 MiB
발상
여기는 직접 적습니다. 아래 셋을 채웁니다.
- 문제를 무엇으로 바꿔 읽었는지
- 먼저 떠오른 방법과 그것이 왜 안 되는지. 입력 크기를 근거로
- 그래서 무엇을 골랐고 왜 그것이면 되는지
풀이
제출한 코드입니다.
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
from collections import deque
N = int(input())
Board = [ list(map(int,input().split())) for n in range(N)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for pos_x in range(N):
for pos_y in range(N):
if (Board[pos_x][pos_y] == 9):
day = 0
Board[pos_x][pos_y] = 0
remain_level = 2
attack_level = 2
while(1):
visited = [ [ 0 for i in range(N)] for l in range(N)]
ans = []
q = deque()
q.append((pos_x,pos_y))
visited[pos_x][pos_y] = 1
t = 0
while(len(q) > 0):
t += 1
for i in range(len(q)):
x, y = q.popleft()
for dir in range(4):
nx, ny = x+dx[dir], y+dy[dir]
if ( 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0 and Board[nx][ny] <= attack_level):
visited[nx][ny] = 1
q.append((nx,ny))
if ( 1 <= Board[nx][ny] < attack_level ):
ans.append((nx,ny))
if(len(ans) != 0 ): break
if ( len(ans) == 0 ):
break
else:
day += t
ans.sort()
pos_x, pos_y = ans[0][0], ans[0][1]
Board[pos_x][pos_y] = 0
visited[pos_x][pos_y] = 1
if (remain_level > 1 ): remain_level -= 1
else:
attack_level += 1
remain_level = attack_level
print(day)
exit()
while(1) 한 바퀴가 몬스터 하나를 없애는 과정입니다. 매번 visited 를 새로 만들고 로봇의 현재 자리에서 BFS를 다시 시작합니다. 판이 바뀌었으니 이전 탐색 결과를 그대로 쓸 수 없습니다.
for i in range(len(q)) 가 층을 나누는 자리입니다. range 안의 len(q) 는 반복이 시작될 때 한 번만 계산되므로, 이 반복은 큐에 들어 있던 그 시점의 칸들만 꺼냅니다. 그 사이에 새로 넣은 칸은 다음 바퀴로 넘어갑니다. 그래서 바깥 while 한 바퀴가 거리 1에 해당하고 t 가 곧 거리가 됩니다.
if(len(ans) != 0 ): break 는 층을 다 펼친 뒤에 검사합니다. 없앨 수 있는 몬스터를 발견하자마자 멈추지 않는 이유는 같은 거리에 다른 몬스터가 더 있을 수 있기 때문입니다. 그 층을 끝까지 펼쳐 놓고 ans.sort() 로 행이 작은 것, 행이 같으면 열이 작은 것을 고릅니다. 튜플 정렬이 문제의 “가장 위, 그다음 가장 왼쪽” 규칙과 그대로 맞습니다.
지나갈 수 있는 칸과 없앨 수 있는 칸의 조건이 다릅니다. 큐에 넣는 조건은 Board[nx][ny] <= attack_level 이고 ans 에 넣는 조건은 1 <= Board[nx][ny] < attack_level 입니다. 레벨이 같은 몬스터는 앞의 조건만 만족해서 지나가되 없애지는 않습니다.
remain_level 은 다음 레벨업까지 남은 몬스터 수입니다. 1보다 크면 하나 줄이고, 1이면 attack_level 을 올린 뒤 새 레벨만큼 다시 채웁니다.
예제 두 개를 넣은 결과입니다.
1
2
3
4
5
6
5
0 0 0 0 0
2 0 0 4 0
0 0 9 0 0
0 0 0 0 0
1 0 0 4 1
1
17
1
2
3
4
3
0 1 1
4 4 4
0 9 0
1
0
복잡도
| 구분 | 값 |
|---|---|
| 입력 크기 | 2 ≤ n ≤ 20, 몬스터의 레벨은 1 이상 6 이하 |
| 시간 | O(n^4) |
| 공간 | O(n^2) |
시간이 O(n^4)인 이유는 BFS 한 번이 O(n^2)이고 그것을 몬스터 수만큼 반복하기 때문입니다. 없앨 수 있는 몬스터는 최대 n^2 - 1마리이므로 while(1) 이 도는 횟수도 O(n^2)입니다. 매 바퀴에서 visited 를 새로 만드는 것과 격자를 훑는 것이 모두 O(n^2)입니다. n = 20이면 20^4 = 160,000이라 제한과 거리가 멉니다.
공간이 O(n^2)인 이유는 Board 와 visited 가 각각 n x n이기 때문입니다. visited 를 바퀴마다 새로 만들지만 이전 것은 버려지므로 동시에 존재하는 것은 하나입니다.
이 복잡도로 제한 안에 드는 근거입니다. n = 20으로 채운 판을 무작위로 300개 만들어 돌려 보니 가장 오래 걸린 것이 파이썬 3.14에서 50ms였습니다. 파이썬 인터프리터가 뜨는 시간까지 포함한 값입니다. 시간 제한 1000ms 안에 넉넉히 듭니다. 채점 결과는 58ms였습니다.