정보
문제 바로가기 [클릭]
난이도: Gold3
관련 개념: #구현 #그래프이론 #그래프탐색 #너비 우선 탐색 #시뮬레이션
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 512 MB |
문제
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
- 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
- 0: 빈 칸
- 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
- 9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
출력
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
예제 입출력 1
입력
1
2
3
4
3
0 0 0
0 0 0
0 9 0
출력
1
0
예제 입출력 2
입력
1
2
3
4
3
0 0 1
0 0 0
0 9 0
출력
1
3
예제 입출력 3
입력
1
2
3
4
5
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
출력
1
14
예제 입출력 4
입력
1
2
3
4
5
6
7
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6
출력
1
60
예제 입출력 5
입력
1
2
3
4
5
6
7
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1
출력
1
48
예제 입출력 6
입력
1
2
3
4
5
6
7
6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9
출력
1
39
코드(파이썬)
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
63
64
65
66
from collections import deque
def bfs(start):
global size, eat
queue = deque([start])
tmp_r = list()
v = {start}
cnt = 0
while queue:
cnt += 1
for _ in range(len(queue)):
loc = queue.popleft()
for d_x, d_y in ((-1,0), (0,-1), (0,1), (1,0)):
n_x, n_y = (loc[0]+d_x, loc[1]+d_y)
if -1 < n_x < n and -1 < n_y < n and (n_x, n_y) not in v:
if 0 < fishbowl[n_x][n_y] < size:
tmp_r.append((n_x, n_y))
elif fishbowl[n_x][n_y] == 0 or fishbowl[n_x][n_y] == size:
v.add((n_x, n_y))
queue.append((n_x, n_y))
if tmp_r:
tmp_r.sort()
t_x, t_y = tmp_r[0]
fishbowl[t_x][t_y] = 0
eat += 1
if eat == size:
size += 1
eat = 0
return cnt, (t_x, t_y)
return -1, start
n = int(input())
fishbowl = [list(map(int, input().split())) for _ in range(n)]
size = 2
eat = 0
result = 0
for i in range(n):
for j in range(n):
if fishbowl[i][j] == 9:
start = (i, j)
break
if any([any(0 < i < size for i in line) for line in fishbowl]):
fishbowl[start[0]][start[1]] = 0
while True:
tmp, start = bfs(start)
if tmp == -1:
break
else:
result += tmp
print(result)
특이사항
- BFS로 해결할 수 있는 문제
- 9(아기상어 위치)가 있는 지점을 start에 저장
- 현재 어항에 먹을 수 있는 물고기가 있다면 bfs 반복
- 먹을 수 있는 물고기가 없다면, -1과 시작 좌표 반환
- 먹을 수 있는 물고기가 있따면, 현재 위치에서 가장 가깝고 먹을 수 있는 물고기를 tmp_r에 저장
- tmp_r에 저장된 물고기 위치 중 가장 위쪽이면서 왼쪽에 해당하는 물고기까지의 거리와 물고기 좌표 반환
- 내 코드(32,504KB, 88ms)와 다른 코드들을 비교한 결과, 비슷한 알고리즘의 구현 형태만 달라 따로 코드는 적지 않겠음
참고문헌
-
Comments powered by Disqus.