16236. 아기상어 문제 바로가기
해결 방법
주요 과정
살아있는 물고기 정보를 담은 fishes 리스트의 for문을 돌며 먹을 수 있는 물고기를 탐색한다.
상어의 크기보다 물고기의 크기가 작다면 queue를 이용하여 상어에서 물고기 위치까지의 거리를 구하여 eat_fishes 리스트에 추가한다.
※ 주의 사항 : 거리 변수의 초기화값은 float(‘inf’) 로 하자! 크기가 작더라도 먹을 수 없을 수 있다는 점!!!
eat_fishes 먹을 수 있는 물고기가 있는지 확인한다.
없다면 종료!
있다면
sort()를 통해 거리가 작을수록, 행이 작을수록, 열이 작을수록 의 정렬을 한다.
이러한 정렬을 하기 위해 eat_fishes에는 [거리, 행, 열, fishes에서의 인덱스값] 순의 정보를 담고 있다.
eat_fishes의 가장 앞의 있는 물고기(먹을 물고기)를 die_fish에 저장하여 거리만큼 time에 더하고 상어 위치를 재정의한다.
또한 먹었기에 fishes에서도 해당 물고기 정보를 제거한다.
이때 먹은 물고기 수를 카운트하여 상어의 크기와 같은 경우 상어의 크기를 더해준다. (먹은 물고기 수는 0으로 초기화!)
구현한 코드
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
N = int(input())
ocean = [list(map(int, input().split())) for _ in range(N)] # ocean : 물고기와 상어의 위치를 표시할 리스트
fishes = [] # 존재하는 물고기에 대한 정보를 [행, 열, 크기] 로 저장
for i in range(N):
for j in range(N):
if ocean[i][j] == 9: # 상어 위치 찾기
shark_y, shark_x = i, j
elif ocean[i][j] > 0: # 물고기 정보 저장하기
fishes.append([i, j, ocean[i][j]]) # [행, 열, 크기] 로 저장
shark_size = 2
time = 0
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
eat_cnt = 0
while True:
eat_fishes = [] # 상어가 먹을 수 있는 물고기를 저장할 리스트
for f in range(len(fishes)):
fy, fx, fs = fishes[f][0], fishes[f][1], fishes[f][2]
if fs < shark_size: # 먹을 수 있는 물고기 조건
q = [[shark_y, shark_x]]
visited = [[0] * N for _ in range(N)]
distance = float('inf') # 주의!! 0으로 두지말자!! 크기가 작더라도 다가갈 수 없을 수 있기에! (제출하자마자 틀린다면 이 조건이 문제!!)
while len(q): # 상어가 물고기를 먹으러 가기 위한 거리를 구하는 과정
sy, sx = q.pop(0)
if [sy, sx] == [fy, fx]:
distance = visited[sy][sx]
break
for d in range(4):
nsy, nsx = sy + dirs[d][0], sx + dirs[d][1]
if 0 <= nsy < N and 0 <= nsx < N and ocean[nsy][nsx] <= shark_size and visited[nsy][nsx] == 0:
q.append([nsy, nsx])
visited[nsy][nsx] = visited[sy][sx] + 1
if distance != float('inf'): # 물고리를 먹을 수 있다면 eat_fishes에 저장하기
eat_fishes.append([distance, fy, fx, f])
if len(eat_fishes) == 0: # 종료조건
break
else:
eat_fishes.sort() # 거리가 작을 수록 같다면 행이 작을 수록 행도 같다면 열이 작을 수록! 정렬
# 물고기 먹기
die_fish = eat_fishes[0] # 먹을 물고기 die_fish 변수에 저장하기
time += die_fish[0] # 먹기 위해 걸린 시간 더하기
# 상어위치 옮기기 (먹은 물고기에 상어 위치를 이전 위치를 0으로 바꾸기)
ocean[die_fish[1]][die_fish[2]] = 9
ocean[shark_y][shark_x] = 0
shark_y, shark_x = die_fish[1], die_fish[2]
# 먹었기에 fishes에서 물고기 정보 제거하기
fishes.pop(die_fish[3])
eat_cnt += 1
# 물고기를 먹은 수가 크기와 같다면 상어 크기 늘려주기
if eat_cnt == shark_size:
shark_size += 1
eat_cnt = 0
print(time)