16236-백준-아기상어

1. 문제 출처

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

16236번: 아기 상어

2. 풀이

 

매번 이동시에 bfs를 이용하여 각 지점의 최소 거리를 구하고 이동하는 작업을 더 이상 이동할 수 있는 거리에 먹이가 없을 때 까지 반복한다...

 

from copy import deepcopy
from collections import deque

# 입력
n = int(input())

space= [0] * n
for i in range(n):
    space[i] = list(map(int,input().split()))
    
# 상하좌우 이동
dx = [0,0,-1,1]
dy = [-1,1,0,0]

#가장 가까운 거리에 있는 물고기 먹기
def eat_fish(temp_space,shark_size):
    '''
    각 지점의 최단 거리가 저장되어 있는 2차원 배열과 상어의 크기를 입력받는다.
    '''
    min_distance = float("inf")
    min_pos = [1,1]
    for i in range(n):
        for j in range(n):
            # 크기가 작은 물고기가 있고 이동 가능 할때
            if (0 < space[i][j] < shark_size) and (temp_space[i][j] > 0):
                if min_distance > temp_space[i][j]:
                    min_distance = temp_space[i][j]
                    min_pos = [i,j]
    # 해당 위치로 상어이동
    space[min_pos[0]][min_pos[1]] = 9
    return min_distance 

def solution():
    # 변수 초기화
    total_dis = 0
    shark_size = 2
    start = 0
    count = 2
    # 이동할 곳이 없을 때까지 반복
    while True:
        # 지점별 최단 거리를 저장할 리스트
        temp_space= [[0] * n for _ in range(n)] 
        for i in range(n):
            for j in range(n):
                # 상어가 있는 지점 찾기
                if space[i][j] == 9:
                    start = [i,j]
                    continue
                # 크기가 큰 물고기 찾기
                if space[i][j] >shark_size:
                    temp_space[i][j] = -1
                    continue
        # 상어의 좌표를 큐에 추가
        queue = deque([start])
        # 상어 출발 좌표 초기화
        space[start[0]][start[1]] = 0
        temp_space[start[0]][start[1]] = 0
        # BFS 실시
        while queue:
            x,y = queue.popleft()
            for idx in range(4):
                xx = x+dx[idx]
                yy = y+dy[idx]
                if 0<=xx<n and 0<=yy<n:
                    if temp_space[xx][yy] == 0:
                        temp_space[xx][yy] = temp_space[x][y] + 1
                        queue.append([xx,yy])
        # 최단 거리 받기
        dis = eat_fish(temp_space,shark_size)
        # 만약 최단 거리가 inf 면 종료
        if dis == float("inf"):
            print(total_dis)
            return
        total_dis +=dis
        count-=1
        # 만약 상어 크기 만큼 물고기를 먹었으면 상어 크기 키우기
        if count==0 and shark_size<7:
            shark_size += 1
            count = shark_size
    
solution()