python 백준 16236 아기상어

백준 16236 아기상어

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

16236번: 아기 상어

1. 문제 : 아기상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

2.접근법

 - 너비 우선 탐색하여 먹이 좌표까지의 최소시간을 찾는다

 - 어려웠던점 일반적인 너비우선탐색을 하면 먹이가 동시에 먹어짐

 - 개선방향 먹을 수 있는 먹이의 위치를 일단 전부 찾고 그중에서 가장 가까운 거리에있는 먹이만 먹는다

 - 같은거리일시 맨좌측 맨우측쪽인 먹이가 우선순위 이다

 - 먹은 먹이 위치로 아기상어의 위치를 바꿔주고 다음 먹이로 다시 탐색한다

import sys
from collections import deque
sys.stdin = open('inputs.text')


n = int(sys.stdin.readline())
matrix = []
count = 0
time = 0
for _ in range(n):
    matrix.append(list(map(int,sys.stdin.readline().split())))

for j in range(n):
    for i in range(n):
        if matrix[j][i] == 9:
            shark_loca = [j,i,0]
            matrix[j][i] = 0
        elif matrix[j][i] < 9 and matrix[j][i] > 0:
            count += 1


def bfs(start):
    global count, init_size

## 아기상어 방문 체크 ##
    visit = [start]
    ans = []
    
    queue = deque([start])

## 아기 상어가 먹을 수 있는 조건의 생선만 전부 먹고 queue가 끝난다 ##
    while queue:
        y,x,day = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            elif matrix[ny][nx] > init_size:
                continue
            elif (matrix[ny][nx] == init_size or matrix[ny][nx] == 0) and [ny,nx] not in visit:
                queue.append([ny,nx,day+1])
                visit.append([ny,nx])
                continue
            elif matrix[ny][nx]>0 and matrix[ny][nx]<init_size and [ny,nx] not in visit:
                ans.append([ny,nx,day+1])
                visit.append([ny,nx])
## 먹을 수 있는 생선이 없으면 끝 ##
    if len(ans) == 0:
        return
    else:
        return ans

## 처음 부터 먹을 수 있는 생선이 없는 경우 프로그램 종료 ##
if count == 0:
    print(0)
    exit()
else:
    init_size = 2
    dy = [0,0,1,-1]
    dx = [1,-1,0,0]
    eat_count = 0
    while True:
        answer = bfs(shark_loca)
## 더이상 먹을 수 없는 생선일 때 None 값을 받고 종료 ##
        if answer == None:
            print(time)
            break
            
## 아기 상어가 먹을 수 있는 여러 생선의 위치 최소값 선택 ##
## 최종 먹을 수 있는 생선까지 도달 하였을 경우의 최소 시간 ##
        answer = deque(sorted(answer, key=lambda x: (x[2],x[0],x[1])))
        min_dis = answer.popleft()
        matrix[min_dis[0]][min_dis[1]] = 0
        time = min_dis[2]
        
## 아기 상어가 생선을 먹은 위치로 위치 수정 ##
        shark_loca = [min_dis[0],min_dis[1],min_dis[2]]
        eat_count += 1
        
## 아기 상어가 커질 수 있는 조건일 경우 size up 후 eat_count 초기화 ##
        if eat_count == init_size:
            init_size += 1
            eat_count = 0