문제
접근
BFS로 접근하면 되는데, 조건이 제법 있는 시뮬레이션 문제이다.
다행히 시간제한은 넉넉해서 전수검사로 BFS를 돌렸다.
프로세스는 다음과 같다.
- 현재 위치에서 BFS를 수행한다.
- 잡아먹을 수 있는 물고기 중에 가장 가까운(같다면 문제에서 제시한 조건) 물고기를 찾는다.
- 잡아먹고 해당 자리로 이동 후 다시 1 수행
이 것을 더 이상 잡아먹을 수 있는 물고기가 없을 때까지 수행한다.
findShark 함수는 최초 1회 상어의 위치를 찾기 위해 수행한다.
compareMove 함수는 문제에서 제시한 가장 가까운(같으면 가장 위, 같으면 가장 왼쪽)을 비교하는 함수이다.
거리, y, x 순으로 재귀적으로 비교해준다.
bfs 함수는 bfs를 수행한다.
visit 배열을 이용하여 거리를 측정했으며, if - continue를 활용하여 이동이 불가능한 경우들을 걸러냈다.
이동하려는 위치에 물고기가 있고, 상어의 크기보다 작으면 compareMove 함수를 통해 다음 이동할 위치를 정한다.
main 함수에서는 루프를 돌며 bfs를 호출해준다.
코드
- 파이썬 코드
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
from collections import deque
def findShark(arr):
for i, line in enumerate(arr):
for j, item in enumerate(line):
if item == 9:
return (i, j)
def compareMove(minMove, nowMove, i):
if minMove[i] < nowMove[i]:
return minMove
elif minMove[i] > nowMove[i]:
return nowMove
else:
return compareMove(minMove, nowMove, i+1)
def bfs(arr, x, y, n, size):
q = deque()
visit = [[-1] * n for _ in range(n)]
q.append((x, y))
visit[y][x] = 0
dx = [0,-1,1,0]
dy = [-1,0,0,1]
minMove = [99999, 0, 0]
while q:
nx, ny = q.popleft()
for ix, iy in zip(dx, dy):
mx = nx + ix
my = ny + iy
if mx < 0 or mx >= n or my < 0 or my >= n:
continue
if arr[my][mx] > size:
continue
if visit[my][mx] >= 0:
continue
visit[my][mx] = visit[ny][nx] + 1
q.append((mx, my))
if arr[my][mx] < size and arr[my][mx] != 0:
minMove = compareMove(minMove, [visit[my][mx], my, mx], 0)
return minMove
def main():
size = 2
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
(y, x) = findShark(board)
cnt = 0
eat = 0
while True:
board[y][x] = 0
move, y, x = bfs(board, x, y, n, size)
if move == 0 or move == 99999:
break
cnt += move
eat += 1
board[y][x] = 9
if eat == size:
size += 1
eat = 0
print(cnt)
if __name__ == "__main__":
main()