백준 16236 아기상어 (Python)

아기상어 뚜루뚜뚜뚜

 

 

문제는 여기!

16236번: 아기 상어

 

삼성 코테는 비교적 효율성에 있어서 자비로운 편이라서 다행이다. 

그래도 0.2초 정도 나왔으니까.. 

 

 

아이디어

1. 물고기 찾는 함수를 BFS/사방탐색으로 구현해준다. 

2. 물고기를 못찾을 때까지 while까지 해당 함수를 돌리기

 

구현 코드

"""
백준 16236 아기상어
https://www.acmicpc.net/problem/16236
Code written by jungwonkkim
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
가장 처음에 아기 상어의 크기는 2
"""
from copy import deepcopy

delta = [(-1,0),(0,-1), (0,1),(1,0)]

def fishfinder(x, y):
    global ate
    global shark
    global fishes
    global time
    global a
    global b
    dist = 1
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[x][y] = True
    queue = [(x,y)] #bfs로 물고기 찾는 것 진행해준다. 
    while queue:
        new_queue = []
        flag = False
        minx = 20
        miny = 20
        for x, y in queue:
            for dl in delta:
                newx = x + dl[0]
                newy = y + dl[1]
                #먹을 수 있는 물고기를 포함해서 무조건 그 자리에 갈 수 있는지부터 확인
                if -1 < newx < N and -1 < newy <N and visited[newx][newy] == False and fishes[newx][newy] <= shark:
                    visited[newx][newy] = True
                    new_queue.append((newx, newy))
                    #내가 먹을 수 있는 물고기자리인지 확인, 물고기있다면 가장 위,왼쪽 좌표로 비교
                    if 0 < fishes[newx][newy] < shark:
                        flag = True
                        if minx > newx:
                            minx = newx
                            miny = newy
                        elif minx == newx:
                            if miny > newy:
                                miny = newy
        if flag:
            fishes[minx][miny] = 0
            a, b = minx, miny
            time += dist
            ate +=1
            if shark == ate:
                shark +=1
                ate = 0
            return True
        queue = deepcopy(new_queue)
        dist +=1
    return False


N = int(input())
fishes = [list(map(int, input().split())) for _ in range(N)]
shark = 2
ate = 0
time = 0
for i in range(N):
    for j in range(N):
        if fishes[i][j] == 9:
            a,b = i, j
            fishes[i][j] = 0
            break
while True:
    if fishfinder(a, b):
        continue
    else:
        break
print(time)