[백준-골드3] 16236번 아기 상어(BFS, 구현, 파이썬)

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

<내 코드>

- 우선 처음으로 아기상어의 좌표를 찾는다.(시작 위치)

- bfs함수를 이용해서 시작좌표를 기준으로 먹을 수 있는 물고기들을 eat 리스트에 담는다.

- eat 리스트에는 거리, x좌표, y좌표를 담게된다.

- bfs 탐색이 끝나면 eat 좌표를 거리, x,y 좌표 순서로 정렬한다.(문제 조건 충족시키기 위해)

- eat이 비어있으면 더이상 먹을 물고기가 없는것이므로 리턴하고

  eat에 원소가 있으면, 정렬 후 가장 앞에 있는 원소를 리턴한다.

 

- 메인 부분에서는 bfs함수가 -1을 리턴할 때까지 bfs함수를 호출한다.

- 이 때 시작 위치를 지정하고, 시작 위치에 대한 bfs함수를 호출한다.

- 그리고 입력받은 물고기가 있는 좌표 ex,ey로 아기상어를 이동시키고, 원래 있던 자리는 빈 자리로 만든다.

- 그 후 다음 시작 지점을 현재 물고기를 먹은 위치로 지정해주고, 물고기 먹은 갯수 카운트를 증가시킨다.

- 물고기 먹은 갯수와 아기상어의 크기가 같으면 아기 상어의 크기를 늘려주고 변수는 초기화한다.

 

- 이때 걸리는 시간은 아기 상어가 물고기를 먹으러 이동한 거리와 같다.(bfs의 최단거리 이용)

from collections import deque
import sys

## 입력
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 아기상어 좌표 찾기, 시작 위치
for i in range(n):
    for j in range(n):
        if graph[i][j]==9:
            graph[i][j]=2 #아기상어 크기
            start = [i,j] #아기상어 시작 좌표

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(i,j):
    visited = [[False]*n for _ in range(n)]
    visited[i][j] = True
    eat = [] #먹을 수 있는 물고기 담을 배열
    dist = [[0]*n for _ in range(n)]
    queue = deque()
    queue.append([i,j])
    
    while queue:
        x,y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0<=nx<n and 0<=ny<n and visited[nx][ny]==False:
                if graph[nx][ny]<=graph[i][j] or graph[nx][ny]==0: #이동 할 수 있으면
                    queue.append([nx,ny])
                    visited[nx][ny] = True
                    dist[nx][ny] = dist[x][y] +1 #거리 증가
                if graph[nx][ny]<graph[i][j] and graph[nx][ny] !=0: #먹을 수 있으면
                    eat.append([nx,ny,dist[nx][ny]])
                    
    # 더 이상 먹을 물고기가 없을 때
    if not eat:
        return -1,-1,-1
    
    #거리순, x좌표(위), y좌표(왼쪽) 순으로 정렬
    #먹을 수 있는 물고기가 1마리 보다 많다면 거리순으로 먹어야함
    #거리가 가까운 물고기가 많다면, 가장 위, 그러한 물고기가 여러마리라면 가장 왼쪽 물고기 먹어야함
    eat.sort(key = lambda x : (x[2], x[0], x[1]))
    return eat[0][0], eat[0][1], eat[0][2] # 좌표와 거리 리턴


eat_cnt = 0 #먹은 물고기 수
time = 0
while True:
    i,j = start[0], start[1]
    ex, ey, dist = bfs(i,j) #가장 먼저 먹을 물고기 위치와 거리를 리턴 받음
    if ex==-1:
        break
    
    graph[ex][ey] = graph[i][j] # 아기상어 이동
    graph[i][j] = 0 # 물고기 먹었으니까 0으로 바꿔줌
    start = [ex,ey] # 먹은 자리부터 다시 시작
    eat_cnt+=1 #먹은 갯수 카운트
    if eat_cnt == graph[ex][ey]: #아기상어의 크기만큼 물고기 먹으면 상어크기 증가
        eat_cnt = 0
        graph[ex][ey] +=1
    time+=dist
    
print(time)

 

입력 예제, bfs 동작 과정