[시뮬레이션] 16236 아기상어

9. 16236 아기상어

9.1. 문제유형

• 시뮬레이션

9.2. 해결과정

• 고려할 조건이 많은 까다로운 문제였다.

1. 상어 위치를 찾고, BFS 탐색을 수행한다.
2. 먹을 물고기가 있는지 없는지를 확인한다.
3. 같은 거리라면 가장 위 물고기를, 그런 물고기가 여러마리라면 왼쪽 물고기를 먼저 먹는다.
4. 상어의 크기 변화 조건 (먹은 물고기 수)을 체크한다.
5. 먹이를 먹은 후, 새로운 위치 탐색을 위해 큐와 방문장소를 초기화한다.
6. 먹이를 먹은 후, 현재까지의 시간을 저장한다.

9.3. 소스코드

from collections import deque

dxs=[-1,1,0,0]
dys=[0,0,-1,1]

def BFS(x, y):
    Q, visited=deque([(x,y)]), set([(x,y)])
    time=0
    shark=2
    eats=0
    answer=0
    flag = False # 먹을 물고기가 있는지를 확인하는 변수

    while Q:
        length = len(Q)

        Q=deque(sorted(Q)) # 정렬하여, 왼쪽 물고기부터 Eat
        for _ in range(length):
            x, y = Q.popleft()

            if graph[x][y] !=0 and graph[x][y]<shark: # 먹을 수 있는 물고기
                graph[x][y]=0
                eats+=1

                if eats == shark: # 크기 변화 조건 충족
                    shark+=1
                    eats=0

                Q, visited = deque(), set([(x,y)]) # 새로운 위치 탐색을 위한 초기화
                flag = True
                answer=time # 현재까지의 시간 저장

            for dx, dy in zip(dxs, dys): # 새 위치에서 상하좌우 탐색
                nx, ny = x+dx, y+dy
                if not (0<=nx<n and 0<=ny<n) or (nx,ny) in visited:
                    continue
                if graph[nx][ny] <= shark: # 이동 가능한 위치일 경우 이동
                    Q.append((nx,ny))
                    visited.add((nx,ny))

            if flag: # 만약 더 이상 먹을 물고기가 없다면
                flag=False
                break

        time+=1 # 시간 1 증가
    return answer


n = int(input())
graph=[list(map(int,input().split())) for _ in range(n)]

x,y=0,0
for i in range(n):
    for j in range(n):
        if graph[i][j]==9:
            x, y = i, j
            graph[i][j]=0

print(BFS(x,y))