[백준 16236] 아기 상어 (Python, BFS, 시뮬레이션)

 

16236번: 아기 상어

처음에 상, 좌, 우, 하 순으로 움직이게 하면 만족 할 줄 알았으나, 

출처) https://coding-w00se.tistory.com/20 

위와 같이 빨간 원에서 초록색을 먹어야하지만 파란 색을 먹는 사태가 벌어져서 거리만큼 bfs를 실행하고 먹을 수 있는 물고기들을 거리순, x,y순으로 정렬하여 선택해야한다.

'''
https://www.acmicpc.net/problem/16236
N * N, 물고기 M마리, 한칸에 최대 한마리
처음 상어크기 2
아기상어 1초 상하좌우 이동
자기보다 큰 물고기칸은 못지나감

더이상 물고기 먹을거 없으면 엄마부름
먹을 물고기 1마리면 그거 먹고, 1마리보다 많으면, 가장 가까운 물고기 먹으러감
 - 가장 위 가장 왼쪽에 있는 물고기 먹음.
 - 자기의 크기와 같은 수의 물고기 먹을때마다 1증가.

result : 엄마 부를 떄까지 시간

'''
import sys
from collections import deque
inp = sys.stdin.readline


def bfs(x,y):
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True
    board[x][y] = 0
    dq = deque()
    dq.append([x,y,0])
    eat = []
    cs, ns = 1,0 #현재 deque 길이, 탐색 횟수. cs*4 = ns가 되면 distance가 1씩 올라갈거임.
    while dq:
        for _ in range(cs):
            cx, cy, cd = dq.popleft() #현재 x,y, distance
            for d in range(4):
                nx, ny, nd = cx + dx[d], cy+dy[d], cd+1
                ns +=1 #탐색 횟수
                if 0<= nx < N and 0<=ny<N and not visited[nx][ny]: # 방문 가능한 곳
                    visited[nx][ny] = True # 방문 표기
                    if board[nx][ny] <= shark: # 이동할 수 있는 곳(자기보다 큰 물고기는 못지나감)
                        dq.append([nx,ny,nd])
                    if 0< board[nx][ny] < shark : #먹는 곳 
                        eat.append([nx,ny,nd])
        if cs * 4 == ns: # (distance 1, 2, 3 ... 마다 먹을 수 있는 물고기 있는지 체크)
            cs = len(dq) # 다음 distance에 쌓인 덱 길이
            ns = 0 # 초기화
            if eat: # 먹을 수 있는 물고기들이 있으면
                eat.sort(key = lambda x: (x[2], x[0], x[1])) #distance, x, y 좌표 순으로 정렬
                return eat[0] #가장 앞에꺼 리턴
            
    return (-1,-1,-1) #갈 곳이 없으면 -1을 리턴하면서 종료



board = []
N = int(inp())
for _ in range(N):
    board.append(list(map(int, inp().rstrip().split() )))
    
shark =2 #상어 최초 크기
eat = 0
for i in range(N):
    for j in range(N):
        if board[i][j] == 9:
            s_x, s_y = i,j #상어 최초 위치 저장

dx = (-1,0,0,1) # 상 좌 우 하
dy = (0,-1,1,0)

result = 0 #time step 

nextFlag =True
while nextFlag:
    x, y, d = bfs(s_x,s_y) #bfs로 다음 물고기 탐색하고
    if (x,y,d )== (-1,-1,-1): # 먹을 물고기 없으면 종료.
        print(result)
        nextFlag=False
    else: # 있으면
        eat +=1 # 먹은거 하나 증가시키고
        if eat == shark: # 만약 자기 크기만큼 먹었으면 크기 키워주고 eat 초기화
            shark+=1
            eat =0
        result +=d #먹은 물고기 거리만큼 time step 증가.
    s_x, s_y = x,y #현재 상어 위치 초기화