16236_아기 상어 (Python)
0. 출처
1. 기록
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> 물고기 위치 및 상어를 이차원 배열로 담는다.
>> 상어의 위치에서 bfs 돌린다. -> 이때 해당 물고기를 찾으면서 시간이 최소인 경우에 그 물고기를 먹는다. 또한 먹은 물고기 좌표를 따로 queue에 담아둔다.
>> 시간이 걸린 물고기가 2개 이상인 경우 각 물고기 좌표를 비교해서 더 작은쪽을 먹고 해당 물고기 좌표를 따로 queue에 담아둔다.
>> 다시 상어의 시작 위치는 queue에 담긴 좌표가 될 것이다.
>> bfs를 다시 돌린다.
>> 어떤 단위 등으로 함수를 나눌 것인지 잘 판단하자 ★
2. 시간복잡도
>>
3. 자료구조
>>
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
3
0 0 0
0 0 0
0 9 0
- 예제 출력 1 -
0
- 예제 입력 2 -
3
0 0 1
0 0 0
0 9 0
- 예제 출력 2 -
3
- 예제 입력 3 -
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
- 예제 출력 3 -
14
- 예제 입력 4 -
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
- 예제 출력 4 -
60
- 예제 입력 5 -
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
- 예제 출력 5 -
48
(3) 코드
# 시간초과
from collections import deque
n = int(input())
graph = list(list(map(int, input().split())) for _ in range(n))
# 상어 이동
def move(q, graph, time, f_graph, size):
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
visited = [[0]*n for _ in range(n)]
while q:
x, y = q.popleft()
# x,y가 찾는 물고기 좌표라면
if graph[x][y] < size and graph[x][y] > 0:
f_graph.append((x, y, visited[x][y]))
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 범위 안에 있고 size가 같거나 작으면
if 0<=nx<n and 0<=ny<n:
if graph[nx][ny] <= size and visited[nx][ny] == 0:
visited[nx][ny] += visited[x][y] + 1
q.append((nx,ny))
if not q:
return f_graph
q = deque()
time = 0
total_time = 0
size = 2
feed = 0
while 1:
# 0. 상어 좌표를 찾는다.
for x1 in range(n):
for y1 in range(n):
if graph[x1][y1] == 9:
s_x = x1
s_y = y1
break
q.append((s_x, s_y))
# 1. 상어 이동
f_graph = []
f_graph = move(q, graph, time, f_graph, size)
# 2. 찾는 물고기 좌표 비교
if len(f_graph) >= 1:
graph[s_x][s_y] = 0
# 시간, x좌표, y좌표 순서의 오름차순으로 정렬 ★
f_graph.sort(key=lambda x : (x[2], x[0], x[1]))
# print(f"f_graph 입니다. {f_graph}")
f_x, f_y, time = f_graph[0]
f_graph = []
graph[f_x][f_y] = 9
feed += 1
total_time += time
time = 0
if size == feed:
size += 1
feed = 0
elif len(f_graph) == 0:
print(total_time)
break
from collections import deque
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
# n = int(6)
# arr = [[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]]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
sx, sy = 0, 0
# 상어의 위치를 찾는다.
for i in range(n):
for j in range(n):
if arr[i][j] == 9:
# 상어위치를 0으로 만들어준다.
arr[i][j] = 0
sx, sy = i, j
break
size = 2
move_num = 0
feed = 0
while True:
q = deque()
q.append((sx, sy, 0))
visited = [[False] * n for _ in range(n)]
flag = 1e9
fish = []
while q:
x, y, count = q.popleft()
# count가 flag(먹이를 찾은 지점까지의 거리)보다 커지는 경우
# 더 이상 찾을 필요가 없으므로 break 한다.
if count > flag:
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 범위를 벗어나는 경우 못지나감
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
# size 보다 큰 경우 못지나감 방문한경우 못 지나감
if arr[nx][ny] > size or visited[nx][ny]:
continue
# size보다 작은 물고기가 있는 경우
if arr[nx][ny] != 0 and arr[nx][ny] < size:
fish.append((nx, ny, count + 1))
print(f"fish 를 먹었습니다 : {fish}")
flag = count
print(f"count 입니다 {count}")
visited[nx][ny] = True
# 내가 생각하는 핵심 부분★
q.append((nx, ny, count + 1))
# 먹이를 먹은 경우(같은 거리)
if len(fish) > 0:
fish.sort()
print(f"먹은 fish입니다 : {fish}")
x, y, move = fish[0][0], fish[0][1], fish[0][2]
move_num += move
feed += 1
# 먹은 fish자리는 0으로 바꿔준다.
arr[x][y] = 0
if feed == size:
size += 1
feed = 0
# 상어의 위치를 바꿔준다. ★
sx, sy = x, y
else:
break
print(move_num)
(4) 정리
생각하는 로직은 맞았는데 생각한 로직대로 구현을 못했다..
문제 구현하고 답안보고 이해하는데까지 3시간걸렸다.
(5) 참고
참고 풀이
