[백준][파이썬] 16236 아기상어 풀이코드

문제 출처 

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

16236번: 아기 상어

 

 

 

접근 방식 및 풀이

- 가장 가까운 물고기를 구하는 것은 BFS를 이용하여 최단거리 찾기

- 가장 가까운 물고기 찾은 위치에서 다음 물고기 찾아가자.

- 짧게 구현하는 것보다 세부 조건들을 까먹지 말고 구현하면서 함수화 해보기 

   - 세부조건 : 나보다 큰 물고기는 지나갈 수 없다. 자신의 크기보다 작은 물고기만 먹는다.

 

 

소스 코드 

import sys
from collections import deque

#sys.stdin = open('text13-3.txt', 'r')

n = int(input())

arr = []
baby_size = 0
baby_x = -1
baby_y = -1
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j] == 9:
            baby_x = i
            baby_y = j


arr[baby_x][baby_y] = 0
#print(arr)
#print(baby_x, baby_y)

times = 0

def print_arr(arr):
    print(' ')
    for k in range(n):
        print(arr[k])

dx = [0,0,-1,1]
dy = [-1,1,0,0]


fish = 0
baby_size = 2
def bfs():

    global baby_size, times

    queue = deque()
    queue.append((baby_x,baby_y))
    distance[baby_x][baby_y] = 0

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            now_x = x + dx[i]
            now_y = y + dy[i]
            if now_x < 0 or now_y < 0 or now_y>=n or now_x >= n :
                continue

            # 큰물고기가 있을때
            if arr[now_x][now_y] > baby_size:
                continue

            # 이미 지나간곳 패쓰
            if distance[now_x][now_y] != -1:
                continue

            distance[now_x][now_y] = distance[x][y] + 1
            #print_arr(distance)
            queue.append((now_x, now_y))
    return distance

INF = int(1e9)

fish_map = [[0]*n for _ in range(n)]
def get_small_fish(size):
    fish_list = []
    for i in range(n):
        for j in range(n):
            if arr[i][j] == size:
                fish_list.append([i,j])
    return fish_list

def find_fish(dist):
    x,y = 0, 0
    min_dist = INF
    # 외
    for i in range(n):
        for j in range(n):
            #print(f'{i},{j} dist : {dist[i][j]}, val : {arr[i][j]}, baby_size: {baby_size}')
            if dist[i][j] != -1 and 1<= arr[i][j] < baby_size:                
                if dist[i][j] < min_dist: # 위에서 왼쪽 저절로 체크 가능
                    x, y = i, j
                    min_dist = dist[i][j]

    # 다 찾아 봤는데도 물고기가 없다?
    if min_dist == INF:
        return None
    else:
        return x, y, min_dist

ate_size = 0

while True:
    distance = [[-1] * n for _ in range(n)]
    distance_map = bfs()
    fish_info = find_fish(distance_map)
    if fish_info == None:
        break
    else:
        baby_x, baby_y = fish_info[0], fish_info[1]
        times += fish_info[2]# 거리가 1당 1초
        
        arr[baby_x][baby_y] = 0
        ate_size += 1
        if baby_size <= ate_size :
            baby_size += 1
            ate_size = 0

 

 

결과