문제 이해
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
종료 조건
- 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹는 조건
- 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
이동 조건
- 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
성장 조건
- 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
문제 접근
이 문제는 하나의 지도를 가지고 있고 최단거리를 이용한 문제기 때문에 BFS를 먼저 생각하게 됐다.
아래의 3가지 단계로 나누어서 접근했다.
- 상어의 현재 위치에서 가장 가까운 먹을 수 있는 물고기를 찾는 함수
- 그 물고기를 먹고 다시 다음 물고기를 찾는 main함수
- 물고기를 먹는 거리를 저장하고 출력하기
문제 풀이
상어의 현재 위치에서 가장 가까운 먹을 수 있는 물고기를 찾는 함수
이 단계에서 BFS를 사용했다.
a,b가 현재 상어의 위치이고 distance는 상어와 먹을 수 있는 물고기의 거리를 저장하는 2차원 배열이다.
eat_list는 상어가 먹을 수 있는 물고기의 좌표와 거리를 저장한 리스트이다.
상어의 위치로부터 상,하,좌,우를 탐색하여 visited를 통해 방문했는지를 확인하고 방문하지 않은 좌표라면 방문했다고 표시한다.
또다시 q에 이동한 좌표를 넣어 그 좌표에서 다시 상,하,좌,우를 확인하고 반복한다.
이렇게 진행했을 때 지도에서 상어가 먹을 수 있는 물고기의 좌표와 거리가 eat_list에 들어가게 되고 이를 반환한다.
dx = [1,0,-1,0]
dy = [0,1,0,-1]
def bfs(a, b):
q = deque()
q.append((a,b))
distance = [[0]*N for _ in range(N)]
eat_list = []
global size
while q:
x,y = q.popleft()
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
if pan[nx][ny] <= size and visited[nx][ny]==0:
q.append((nx,ny))
visited[nx][ny] = 1
distance[nx][ny] = distance[x][y] + 1
if pan[nx][ny] < size and pan[nx][ny]!=0:
eat_list.append((nx,ny,distance[nx][ny]))
return eat_list그 물고기를 먹고 다시 다음 물고기를 찾는 main함수
이렇게 반환된 eat_list를 lambda를 이용하여 정렬한다. 그 이유는 아까 먹는 조건에서
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
라는 조건이 있기 때문에 거리,x,y순으로 우선순위가 있다.
이를 위해 정렬하고 가장 적합한 물고기를 nx,ny,distance에 저장한다.
이렇게 저장한 값을 x,y에 저장한다.
그 후 이를 반복해야 되기 때문에 while문을 사용하여 계속 반복한다.
또한 성장조건을 위해서 size와 eat을 사용하여 먹은 물고기의 개수를 eat에 저장하고 size와 eat이 같아진다면 size를 1증가, eat을 다시 0으로 초기화한다.
while 무한루프를 탈출하기 위한 조건으로는 eat_list의 개수가 0이면 탈출하도록 설정한다.
eat_list의 개수가 0이라는 것은 더이상 먹을 수 있는 물고기의 개수가 없다는 것을 의미하기 때문에 이때 엄마 상어를 부르며 while문은 종료된다.
for i, line in enumerate(pan):
for j, value in enumerate(line):
if value == 9:
x=i #초기 상어의 위치 파악
y=j
pan[x][y] = 0
size = 2 # 초기값
eat = 0 # 초기값
while 1:
visited = [[0]*N for _ in range(N)] #방문했는지를 저장하는 2차원 배열
eat_list = bfs(x,y) #반환된 eat_list저장
if len(eat_list)<1: # 먹을 수 있는 리스트가 없으면 무한루프 탈출
break
eat_list.sort(key=lambda x:(-x[2],-x[0],-x[1])) # 오름차순 정렬 우선순위: 거리, x, y 순
if len(eat_list)<1: # 먹을 수 있는 리스트가 없으면 무한루프 탈출
break
nx,ny,distance = eat_list.pop()
# 먹은 좌표로 이동시킴
x = nx
y = ny
pan[x][y] = 0
count += distance # 소요시간 count에 더함
eat += 1
if size==eat:
size += 1
eat = 0물고기를 먹는 거리를 저장하고 출력하기
count += distance # 소요시간 count에 더함while문 내에서 count에 distance를 더해주고 while문을 탈출했을 때 count를 출력한다.
제출 코드
import sys
from collections import deque
N = int(sys.stdin.readline())
pan = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
def bfs(a, b):
q = deque()
q.append((a,b))
distance = [[0]*N for _ in range(N)]
eat_list = []
global size
while q:
x,y = q.popleft()
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
if pan[nx][ny] <= size and visited[nx][ny]==0:
q.append((nx,ny))
visited[nx][ny] = 1
distance[nx][ny] = distance[x][y] + 1
if pan[nx][ny] < size and pan[nx][ny]!=0:
eat_list.append((nx,ny,distance[nx][ny]))
return eat_list
count = 0
for i, line in enumerate(pan):
for j, value in enumerate(line):
if value == 9:
x=i
y=j
pan[x][y] = 0
size = 2
eat = 0
while 1:
visited = [[0]*N for _ in range(N)]
eat_list = bfs(x,y)
if len(eat_list)<1: # 먹을 수 있는 리스트가 없으면 무한루프 탈출
break
eat_list.sort(key=lambda x:(-x[2],-x[0],-x[1])) # 오름차순 정렬 우선순위: 거리, x, y 순
if len(eat_list)<1: # 먹을 수 있는 리스트가 없으면 무한루프 탈출
break
nx,ny,distance = eat_list.pop()
# 먹은 좌표로 이동시킴
x = nx
y = ny
pan[x][y] = 0
count += distance # 소요시간 count에 더함
eat += 1
if size==eat:
size += 1
eat = 0
print(count)