문제
성능 요약(python 3)
3달전 : 메모리: 32564 KB, 시간: 128 ms
오늘 : 메모리: 32580 KB, 시간: 336 ms
분류
너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation)
분석
이미 한 번 풀었던 이 문제를 두고 2시간이나 골 머리를 썩혔다...! 이유는
상-좌-우-하로 찾아야 하고, BEST로 찾으려면 일단 같은 거리의 고기는 모두 뒤져야 된다
=> 아까는 생각하지 못해 BFS로 MAP을 다 뒤졌지만, 이제 생각해보니 현재 방문거리를 저장해놓고, 찾은 고기가 있는데 그 거리보다 멀리가면 while문을 벗어나는 방법을 사용하면 시간을 훨~씬 단축할 수 있다.
=> 오... 예전 CODE에는 그게 있구나...
💻예전 sudo-CODE
1. 2차원 리스트인 MAP을 모두 돌아다니며 상어의 현재위치와, 물고기들의 위치를 저장해준다.
2. 물고기를 다 잡아먹을 때까지 while문을 돌린다. 방문 처리 리스트를 만들어준다.
2-1. for문을 돌린다.
2-1-1. fish 리스트에서 아기 상어보다 사이즈가 작은 물고기들을 check_fish List에 적어준다. 그리고 end_count를 채워준다.
2-1-2. 아기 상어랑 사이즈가 같거나 크면 방문처리를 해줘서 BFS때 못지나가게 만든다.
2-1-3. 위 두가지에 해당하지 않으면 end_count를 채워준다.
2-2. end_count와 물고기의 개수가 같으면 먹을 수 있는 물고기(나보다 작은 물고기)가 없는 것이기 때문에 종료해준다.
2-3. 아니라면 bfs를 돌려준다. q에 상어의 첫 위치를 넣어주고 q가 비워지기 전엔 계속 while문을 돈다
2-3-1. BFS를 돌며 거리를 재면서 돈다. 이 때 방문한 위치에 확인할 고기가 있고, 현재 물고기를 찾은 최소 거리보다 현재 방문한 거리가 작으면 먹을 물고기 리스트에 넣어준다.
2-3-2. q가 끝났는데 먹을 물고기가 있다면,
2-3-2-1. 물고기가 여러마리라면 제일 상단이며, 제일 상단인 물고기가 여러마리라면 제일 왼쪽에 있는 물고기를 먹어준다(물고기 리스트에서 먹은 물고기를 지워준다).
3-1. BFS를 돌고 fish가 없으면 종료한다💻오늘 sudo-CODE
1. 2차원 리스트인 MAP을 모두 돌아다니며 상어의 현재위치를 찾아준다.
2. 체크 변수가 0 일 때까지 돈다.
2-1. BFS문을 돌려 먹을 물고기 리스트와 방문 리스트를 return 받는다.
2-1-1. BFS를 돌며 거리를 재면서 돈다. 이 때 방문한 위치에 현재 상어의 크기보다 작은 물고기가 있다면 먹을 물고기 리스트에 거리와 물고기 좌표를 넣어준다.
2-2. return 받은 물고기들 중 최소 거리 물고기를 찾는다.
2-2-1. 최소 거리 물고기가 여러 마리라면 제일 상단에 위치하고, 동일하다면 제일 좌측 물고기를 찾아준다.
2-3. 시작 위치 값을 먹은 물고기 위치로 해주고, 최종 거리에 현재 이동한 거리를 더해준다.
2-4. 먹은 물고기 개수를 늘려주고, 상어 크기만큼 먹었다면 상어 크기를 키워준다.
2-5. 먹은 물고기를 MAP에서 지워주고 다시 BFS를 돈다
3-1. BFS문의 물고기 리스트가 빈 채로 return 했다면 종료한다.😊What I Learned
1. e.sort(key=lambda x : x[원하는 index])
sort는 이차원 인덱스에서 보통 행 리스트의 첫 번째 요소를 기준으로 정렬해준다! 근데 특정 순서 요소를 기준으로 정렬해주고 싶을 때는 lambda 함수를 이용하면 가능하다.
💻CODE
예전 코드
from collections import deque
def BFS():
global baby_size, time, baby, temp
my_fish = []
move_cnt = 1000
queue = deque([baby])
visited[baby[0]][baby[1]] = True
while queue:
now_x, now_y = queue.popleft()
if bfs_lst[now_x][now_y] > move_cnt:
break
for i in range(4):
x = now_x + direc_x[i]
y = now_y + direc_y[i]
if 0<=x<N and 0<=y<N and visited[x][y] == False:
queue.append([x,y])
visited[x][y] = True
bfs_lst[x][y] = bfs_lst[now_x][now_y] + 1
if [x,y] in cheak_fish and move_cnt >= bfs_lst[x][y]:
my_fish.append([x,y])
move_cnt = bfs_lst[x][y]
if my_fish:
if len(my_fish) > 1:
my_fish.sort(key=lambda x : x[1])
my_fish.sort(key=lambda x : x[0])
my_fish = [my_fish[0]]
x = my_fish[0][0]
y = my_fish[0][1]
time += bfs_lst[x][y]
temp += 1
if temp == baby_size:
baby_size += 1
temp = 0
map_lst[x][y] = 0
baby = [x,y]
fish.remove([x,y])
return 1
return 0
N = int(input())
map_lst = [[0] for _ in range(N)]
fish = []
for i in range(N):
map_lst[i] = list(map(int, input().split()))
for j in range(N):
if map_lst[i][j] == 9:
# baby = [i,map_lst[i].index(9)]
baby = [i,j]
map_lst[baby[0]][baby[1]] = 0
elif map_lst[i][j] > 0:
fish.append((i,j))
direc_x = [-1, 1, 0, 0]
direc_y = [0, 0, -1, 1]
baby_size = 2
end_cnt = 0
time = 0
temp = 0
while fish:
cheak_fish = []
end_cnt = 0
visited = [[False] * N for _ in range(N)]
for f in fish:
if map_lst[f[0]][f[1]] > baby_size:
visited[f[0]][f[1]] = True
end_cnt += 1
elif map_lst[f[0]][f[1]] != 0 and map_lst[f[0]][f[1]] < baby_size:
cheak_fish.append(f)
else:
end_cnt += 1
if end_cnt == len(fish):
break
bfs_lst = [[0] * N for _ in range(N)]
result = BFS()
if result == 0:
break
print(time)오늘 코드
import sys
from collections import deque
def BFS(start, size_eat):
visited = [[0] * N for _ in range(N)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
q = deque([start])
visited[start[0]][start[1]] = 1
temp = []
while q:
x, y = q.popleft()
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < N and 0 <= ny < N:
if (not MAP[nx][ny] or MAP[nx][ny] == size_eat[0]) and not visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
q.append([nx, ny])
elif 0 < MAP[nx][ny] < size_eat[0] and not visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
q.append([nx, ny])
temp.append([visited[nx][ny], nx, ny])
return temp, visited
N = int(sys.stdin.readline())
check = [[False] * N for _ in range(N)]
MAP = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
baby = [2, 0]
for i in range(N):
for j in range(N):
if MAP[i][j] == 9:
start = [i, j]
MAP[i][j] = 0
count = 0
end = 0
while not end:
e, visit = BFS(start, baby)
if e:
V_min = min(e)
if e.count(V_min) > 1:
min_N = [N, N]
for idx in e:
if min_N[0] == idx[1]:
if min_N[1] > idx[2]:
eat_fish = idx[1:]
elif min_N[0] > idx[1]:
eat_fish = idx[1:]
else:
eat_fish = e[e.index(V_min)][1:]
start = eat_fish
count += visit[eat_fish[0]][eat_fish[1]] - 1
baby[1] += 1
if baby[0] == baby[1]:
baby = [baby[0] + 1, 0]
MAP[eat_fish[0]][eat_fish[1]] = 0
else:
end = 1
print(count)
HAPPY 💌